一、Map

graph TD Map --- HashMap; Map --- HashTable; Map --- TreeMap; Map --- EnumMap; HashMap --- LinkedHashMap; HashTable --- Properties;

	key可以为空	value可以为空	key可以重复	value可以重复	是否有序	线程是否安全	底层数据结构
HashMap	✓	✓	✗	✓	无序	不安全	java7:数组+链表。java8:数组+链表+红黑树
LinkedHashMap	✓	✓	✗	✓	存取有序	不安全	HashMap基础上+双向链表
TreeMap	✗	✓	✗	✓	自然顺序排序	不安全	红黑树
Hashtable	✗	✗	✗	✓	无序	安全	数组 + 链表

在HashMap和LinkedHashMap等实现类中，键可以为null。由于HashMap使用哈希表来存储键值对，允许一个键为null，且将其映射到哈希表的索引0上。

在TreeMap实现类中，键不能为null。TreeMap基于红黑树实现，要求键必须实现Comparable接口，因此不允许为null。

1.1 HashMap

内部结构分析

HashMap是一个集合，键值对的集合,源码中每个节点用Node<K,V>表示

1
2
3
4
5


static class Node<K,V> implements Map.Entry<K,V> {
   final int hash;
   final K key;
   V value;
   Node<K,V> next;

Node是一个内部类，这里的key为键，value为值，next指向下一个元素，可以看出HashMap中的元素不是一个单纯的键值对，还包含下一个元素的引用。

HashMap的数据结构为 数组+(链表或红黑树) ，数组默认长度为16，每次扩容都是2倍，负载因子为0.75，也就说第一次扩容数组长度为16*0.75=12。

每条链表也叫做桶(bucket)，红黑树是为了提高查询效率
存放元素的时候会先根据key的hash值去计算数组下标，如果这个下标下没有元素，就创建一个Node节点放进去
如果数组下标有数据，先判断是否与链表中的key相同，相同的话替换元素的value；不同的话插在链表的尾节点。注意：同一个链表中的节点只是说数组下标相同，但不一定是发生了hash冲突的，有可能hash值不同
链表长度大于等于8，且当数组长度大于等于64，会把链表转为红黑树，否则会优先触发扩容(对数组扩容，目的是减少单个桶中元素的数量)。这意味着需要同时满足两个条件，链表才会转化为红黑树。红黑树本质是一颗自平衡的二叉查找树，查找时间复杂度为o(logn)

阈值 8 的原因

如果链表过长，查找性能会退化为 O(n)。

转换为红黑树后，查找性能提升到 O(log n)。

选择 8 作为阈值是基于性能和内存的折中。链表转红黑树会增加一定的内存开销，因此只有链表足够长才转换。

put过程分析

图片来自：https://www.jianshu.com/p/d04edc8aaf0f

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72


public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素（处理hah冲突）
    else {
        Node<K,V> e; K k;
        // 判断table[i]中的元素是否与插入的key一样，若相同那就直接使用插入的值p替换掉旧的值e。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
        // 判断插入的是否是红黑树节点
        else if (p instanceof TreeNode)
            // 放入树中
            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);
                    // 结点数量达到阈值(默认为 8 )，执行 treeifyBin 方法
                    // 这个方法会根据 HashMap 数组来决定是否转换为红黑树。
                    // 只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是对数组扩容。
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) {
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

resize 方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80


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;
        }
        // 没超过最大值，就扩充为原来的2倍
        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 {
        // signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize上限
    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) {
        // 把每个bucket都移动到新的buckets中
        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 {
                    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;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

Hash冲突

HashMap使用拉链法（Chaining）来解决哈希冲突。当发生哈希冲突时，即多个键被映射到同一个哈希桶的位置上，HashMap会在该位置上维护一个链表（或者更准确地说，是一个链表数组），将具有相同哈希值的键值对存储在同一个链表中。

具体的解决过程如下：
1. 当需要插入一个键值对时，HashMap会先计算键的哈希值，并根据哈希值找到对应的哈希桶（也称为槽位）。
2. 如果该槽位为空，即没有其他键值对存在，直接将键值对插入到该槽位上。
3. 如果该槽位已经存在一个或多个键值对，那么会遍历链表，比较键的值：
  - 如果存在键的值与要插入的键值对的键相等，则更新该键值对的值。
  - 如果遍历完链表仍未找到相等的键值对，则将新的键值对追加到链表的末尾。
在哈希表的查询操作中，HashMap会根据键的哈希值定位到对应的哈希桶，然后遍历链表查找具有相同键的键值对。

当链表的长度过长时，为了提高查询效率，HashMap会将链表转换为红黑树。当链表长度大于等于8，数组长度大于64时会将链表转换为红黑树，从而提高搜索和插入的性能。当红黑树的节点数量减少到6个以下时，又会将红黑树转换回链表。

通过使用链表和红黑树来处理哈希冲突，HashMap可以有效地解决哈希冲突并提供高效的键值对存储和检索。
get 过程分析

首先，根据要获取的键通过哈希函数计算出哈希值。
根据哈希值计算出数组的索引位置。
在该索引位置上检查是否存在键值对。
如果该位置为空，则说明没有找到对应的键，返回null。
如果该位置不为空，则需要进一步判断是否存在相同的键。
如果找到相同的键，则返回对应的值。
如果该位置存在多个键值对，则需要遍历链表（或红黑树）来查找对应的键。
如果找到相同的键，则返回对应的值。
如果遍历完整个链表（或红黑树）仍然没有找到相同的键，则返回null。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判断第一个节点是不是就是需要的
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 判断是否是红黑树
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);

            // 链表遍历
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
} 

1.2 LinkedHashMap

LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

1.3 TreeMap

TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

二、Iterable

graph TD Iterable --- Collection; Collection --- Queue; Collection --- List; Collection --- Set; List --- ArrayList; List --- LinkedList; List --- Vector; Deque --- LinkedList; Set --- HashSet; Set --- TreeSet; Set --- EnumSet; Queue --- Deque; Queue --- PriorityQueue; Vector --- Stack; HashSet --- LinkedHashSet;

	值可以为空	值可否重复	是否有序	线程是否安全	底层数据结构	特点
ArrayList	✓	✓	存取有序	不安全	数组	查询快, 增删慢
LinkedList	✓	✓	存取有序	不安全	双向链表	查询慢, 增删快
Vector	✓	✓	存取有序	安全	数组	查询快, 增删慢
HashSet	✓	✗	无序	不安全	Hash表结构	底层的实现其实是一个 java.util.HashMap
LinkedHashSet	✓	✗	存取有序	不安全	链表和哈希表组合的一个数据存储结构	元素唯一且存取有序
TreeSet	✗	✗	自然顺序排序	不安全	二叉树结构	保证元素的唯一, 可以对元素进行排序

2.1 ArrayList

ArrayList允许存放null元素，底层通过数组实现的有序集合。ArrayList底层数组默认初始化长度为10，元素超过此长度后会自动扩容，容量将扩展到原来的1.5倍。

自动扩容代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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);
}

2.2 LinkedList

LinkedList底层通过双向链表实现，双向链表的每个节点用内部类Node表示。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。
在这里没有所谓的哑元，当链表为空的时候first和last都指向null。

内部类Node:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

2.3 HashSet

HashSet是对HashMap的简单包装，对HashSet的函数调用都会转换成合适的HashMap方法，详细请看HashMap。

2.4 LinkedHashSet

LinkedHashSet是对LinkedHashMap的简单包装，对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法，详细请看LinkedHashMap。

2.5 TreeSet

前面已经说过TreeSet是对TreeMap的简单包装，对TreeSet的函数调用都会转换成合适的TreeMap方法，详细请看TreeMap。

java基础03-集合

文章目录