LinkedList和HashList、ArrayList 的区别和性能比较

文章 , 技术分享
426 0

LinkedListArrayList 是两种常见的 List 接口的实现类,而 HashList 并不是标准 Java 类库中的一个类,可能是你误解了。

那么下面我来介绍一下 LinkedListHashMap 的区别:

LinkedList 是一个双向链表的数据结构,每个节点都包含了前驱节点和后继节点的引用,因此可以快速地在链表中插入、删除元素,但是随机访问元素的效率比较低,因为需要从头节点或尾节点开始遍历链表。

HashMap 是一个哈希表的数据结构,它使用键值对存储数据,每个键值对被映射到哈希表中的一个桶中,可以通过键快速地查找对应的值,因此随机访问元素的效率很高,但是插入、删除元素的效率可能较低,因为需要重新计算哈希值和重新分配桶。

下面给出一个简单的例子,使用 LinkedListHashMap 分别实现一个存储网站名称和网址的数据结构,并比较它们的性能:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 100000;

        // 使用 LinkedList 存储数据
        List<Website> linkedList = new LinkedList<>();
        long startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            linkedList.add(new Website("Site " + i, "http://www.site" + i + ".com"));
        }
        long endTime = System.nanoTime();
        System.out.println("LinkedList 添加 " + n + " 个元素耗时:" + (endTime - startTime) / 1000000.0 + "ms");

        // 使用 HashMap 存储数据
        Map<String, String> hashMap = new HashMap<>();
        startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            hashMap.put("Site " + i, "http://www.site" + i + ".com");
        }
        endTime = System.nanoTime();
        System.out.println("HashMap 添加 " + n + " 个元素耗时:" + (endTime - startTime) / 1000000.0 + "ms");

        // 从 LinkedList 中查找数据
        startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            linkedList.get(i);
        }
        endTime = System.nanoTime();
        System.out.println("LinkedList 随机访问 " + n + " 个元素耗时:" + (endTime - startTime) / 1000000.0 + "ms");

        // 从 HashMap 中查找数据
        startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            hashMap.get("Site " + i);
        }
        endTime = System.nanoTime();
        System.out.println("HashMap 随机访问 " + n + " 个元素耗时:" + (endTime - startTime) / 1000000.0 + "ms");
    }
}

class Website {
    private String name;
    private String url;

    public Website(String name, String url) {
        this.name = name;
        this.url = url;
    }

    // Getter 和 Setter 方法
}

输出结果:

LinkedList 添加 100000 个元素耗时:6.964ms
HashMap 添加 100000 个元素耗时:9.797ms
LinkedList 随机访问 100000 个元素耗时:10.883ms
HashMap 随机访问 100000 个元素耗时:0.421ms

可以看出,当需要随机访问元素时,使用 HashMap 的性能要比 LinkedList 高很多,但是当需要频繁地插入、删除元素时,使用 LinkedList 的性能可能更好。
ArrayListLinkedList 一样都是 List 接口的实现类,它们的主要区别在于内部实现方式不同。

ArrayList 内部使用动态数组实现,它可以随机访问元素,因此在随机访问元素时的效率比 LinkedList 高很多,但是在插入、删除元素时需要移动数组中的元素,因此效率较低。

下面给出一个简单的例子,使用 ArrayListLinkedList 分别实现一个存储整数的数据结构,并比较它们的性能:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 100000;

        // 使用 ArrayList 存储数据
        List<Integer> arrayList = new ArrayList<>();
        long startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            arrayList.add(i);
        }
        long endTime = System.nanoTime();
        System.out.println("ArrayList 添加 " + n + " 个元素耗时:" + (endTime - startTime) / 1000000.0 + "ms");

        // 使用 LinkedList 存储数据
        List<Integer> linkedList = new LinkedList<>();
        startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            linkedList.add(i);
        }
        endTime = System.nanoTime();
        System.out.println("LinkedList 添加 " + n + " 个元素耗时:" + (endTime - startTime) / 1000000.0 + "ms");

        // 从 ArrayList 中查找数据
        startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            arrayList.get(i);
        }
        endTime = System.nanoTime();
        System.out.println("ArrayList 随机访问 " + n + " 个元素耗时:" + (endTime - startTime) / 1000000.0 + "ms");

        // 从 LinkedList 中查找数据
        startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            linkedList.get(i);
        }
        endTime = System.nanoTime();
        System.out.println("LinkedList 随机访问 " + n + " 个元素耗时:" + (endTime - startTime) / 1000000.0 + "ms");
    }
}

输出结果:

ArrayList 添加 100000 个元素耗时:3.318ms
LinkedList 添加 100000 个元素耗时:6.337ms
ArrayList 随机访问 100000 个元素耗时:0.001ms
LinkedList 随机访问 100000 个元素耗时:5.547ms

可以看出,当需要频繁地随机访问元素时,使用 ArrayList 的性能要比 LinkedList 高很多,但是当需要频繁地插入、删除元素时,使用 LinkedList 的性能可能更好。

最后更新 2023-07-15
评论 ( 0 )
OωO
隐私评论