开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Java的Set接口和List接口的详解 -> 正文阅读

[数据结构与算法]Java的Set接口和List接口的详解

Iterable(I)

Collection(I)

Collection 接口常用的方法有以下几个

add
remove
contains 查找某个元素是否存在
size
isEmpty 判断是否为空
clear 清空
addAll 添加多个元素 
containsAll
removeAll
get

List(I)

三种遍历方式：

使用iterator
增强for循环
普通的for

    //使用iterator
    Iterator iterator = arrayList.iterator();
    while(iterator.hasNext()){
        System.out.println(iterator.next());
    }

    //增强for循环
    for(Object e : arrayList){
        System.out.println("List+" + e);
    }

    //普通for循环
    for (int i = 0;i < arrayList.size();i++){
        System.out.println("list+" + arrayList.get(i));
    }
}

Vector

Vector 底层也是一个对象数组，protected Object[] elementData;

Vector 是线程同步的，即线程安全，Vector类的操作方法带有synchronized

Vector 是安全的，但是效率低

在开发中，需要线程同步安全时，考虑使用Vector

Vector的扩容机制
- 如果是无参构造，默认是10 满后，就按照两倍扩容
- 如果指定大小，每次直接按照两倍扩容
- 如果执行的大小，还指定了扩容的大小，则每次按照指定的扩容的大小进行扩容。

ArrayList

ArrayList 是由数组来实现的数据存储的，它基本等同于Vector，ArrayList是线程不安全的，但是执行效率高，因为它没有锁，在多线程的情况下，不建议使用ArrayList

ArrayList扩容机制

ArrayList维护了一个Object类型的数组elementData

transient Object[] elementData
当创建ArrayList的时候，如果使用的是无参构造器，则初始elementData容量为0，第一次添加，则扩容elementData为10，如果需要再次扩容，则扩容的elementData为1.5倍，那为什么是1.5倍，代码如下

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

LinkedList

LinkedList 底层结构
- LinkedList 底层维护了一个双向链表
- LinkedList中维护了两个属性first和last分别指向首结点和尾节点
- 每个节点（Node对象），里面又维护了prev、next、item 三个属性，其中通过prev指向前一个，通过next指向后一个节点，最终实现双向链表
- 所以LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率高一些

LinkedList也是线程不安全的，没有实现同步.

Set(I)

Set接口的基本介绍

无序（添加和取出的顺序不一样），没有索引
不允许重复元素，所以最多包含一个null

Set接口常用的方法，和List接口差不多，因为都是Collection的子接口

Set接口的遍历方式

可以使用迭代器
增强for
不能使用索引的方式来获取。

        Iterator iterator = s.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }

        for (Object obj : s){
            System.out.println(obj);
        }

注意：虽然是无序的，只是取出的顺序不是添加的顺序，但每次取出都是固定的，是不变的。

TreeSet

HashSet

HashSet 实现了Set接口
HashSet 实际上是HashMap，源码如下

    public HashSet() {
        map = new HashMap<>();
    }

可以存放null值，但是只能有一个null
HashSet不保证元素是有序的，取决于hash后，再确定索引的结果。
不能有重复元素/对象

Hash的底层是HashMap，HashMap的底层是（数组+链表+红黑树）

HashSet底层机制
- HashSet底层是HashMap
- 添加一个元素时，先得到hash值-会转成-》索引值
- 找到存储数据表table（一个数组），看到这个索引位置是否已经存放了元素
- 如果没有，直接加入
- 如果有，调用equals（程序猿可以进行重写）比较，如果相同，就放弃添加，如果不相同，则添加到最后
- 在java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8)，并且table的大小>=MIN_TREEIFY_CAPACITY(默认64)，就会进行树化（红黑树）
HashMap的扩容
- HashSet 底层是HashMap，第一次添加时，table数组扩容到16，临界值（threshold）是16*加载因子（loadFactor）是0.75 = 12（是超过12个的时候，也就是添加完第13个的时候，就会进行判断，然后扩容）
- 如果table数组使用到了临界值12。就会扩容到16*2 = 32，新的临界值就是32* 0.75=24,依次类推
- 在java8中，如果一条链表的元素个数到达TREEEIFY_THRESHOLD(默认是8)，并且table的大小>=MIN_TREEIFY_CAPACITY(默认是64)，就会进行树化（红黑树），否则仍然采用数组扩容机制。

public class demo04 {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("java");
        hashSet.add("php");
        hashSet.add("java");
        System.out.println("set=" + hashSet);
    }
}

源码解读

执行 HashSet（）

public HashSet() {
    map = new HashMap<>();
}

执行add（）方法

public boolean add(E e) {//e : java
    return map.put(e, PRESENT)==null;//PRESENT 是一个对象（static）PRESENT = new Object()
}

3.执行put（）方法

public V put(K key, V value) {//key： java ；value：Object
    return putVal(hash(key), key, value, false, true);
}

在这段代码中，有一个hash（key）实际就是计算”java“的哈希值，但他不等价于hashcode（注意：不是hashcode 不是hashcode），因为他是把计算出来的hashcode，无符号右移16位，所得到的一个哈希值，是为了降低hash冲突几率，代码如下

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

4.核心代码

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)//table:Node<K,V>[]
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)//计算出来一个哈希值，并得到一个索引。并判断为不为空
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;//如果哈希值相等，并且key相等（== （比较是否指向了同一个对象）和 equals （是否相等）满足之中一种就行） 那么就被认定完全一样的。
        else if (p instanceof TreeNode)
            //判断p是不是一颗红黑树
            //如果是一颗红黑树，就调用putTreeVal 进行添加
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //顺着该单向链表一直往下，对每一个节点，进行对比，看是否有相等的。
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //在这是进行树化的代码，加上链表头，在根据代码的顺序，也就是已经存在第九个节点的时候进行树化了。
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

table:就是HashMap的一个Node类型的数组 Node<K,V>[]

在其中会进入到一个resize方法，代码如下

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY; //16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//临界值
        //这个变量表明，当你的空间达到这个临界值的时候，就回去扩容，并不是空间满了，才去扩容。
        //考虑冲突机会与空间利用率的平衡，取得的最优解，利用概率算的。
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

DEFAULT_INITIAL_CAPACITY： static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
DEFAULT_LOAD_FACTOR ：临界因子 static final float DEFAULT_LOAD_FACTOR = 0.75f;

LinkedHashSet

LinkedHashSet的全面说明
- LinkedHashSet是HashSet的子类
- LinkedHashSet底层是一个LinkedHashMap，底层维护了一个数组 + 双向链表
- LinkedHashSet 根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的
- LinkedHashSet不允许添加重复的元素
LinkedHashSet底层机制
- 在LinkedHashSet 中维护了一个hash表和双向链表（LinkedHashSet有head(链表头)和tail（链表尾））
- 在每一个节点有pre和next属性，这样可以形成双向链表
- 在添加一个元素时，先求hash值，再求索引，确定该元素在hashtable的位置，然后将添加的元素加入到双向链表（如果已经存在，不添加[原则和hashset一样]）
tail.next = newElement

newElement.pre =tail

tail = newElement
- 这样的话，我们遍历LinkedHashSet 也能确保插入顺序和遍历顺序一致。
源码解读

LinkedHashSet 加入顺序和去除元素/数据的顺序一致的。
LinkedHashSet 底层维护的是一个LinkedHashMap（HashMap子类）
LinkedHashSet 底层结构（数组table+双向链表）
第一次添加时，直接将数组table 扩容到16，存放的结点类型 LinkedHashMap$Entry
数组是 HashMap $N o d e [] 存放的元素 / 数据是 L i n k e d H a s h M a p$ Entry

这就表明这两个之间是继承关系，继承关系是在内部类完成的。

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}