数据结构分析

数据结构：数组+链表（或红黑树）

数组：Entry<K,V> implements Map.Entry<K,V>实力数组

链表：Entry内的next指向Entry实现

value是按数组存放的，int hash = hash(key.hashCode()); int i = indexFor(hash, table.length) 将value放到table中i位置，这样能快速找到数据存储位置，效率高。但是又涉及到数组中同一index存放不同的数据的情况

关于链表解决冲突：

hash-chain.jpg

JAVA为什么两个不同对象的hashCode有可能相同

public V put(K key, V value) {  
        if (key == null)  
            return putForNullKey(value);  
        int hash = hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
                V oldValue = e.value;  
                e.value = value;  
                return oldValue;  
            }  
        }  
        modCount++;  
        addEntry(hash, key, value, i);  
        return null;  
    }

从原码分析：

map存数据的时候，是按table存储的，如果相同index下的entry的hash和key都一样，覆盖就行了。但是不同的key值可能hash值相同，但是也要存储到对应的index下。这就是hash冲突的根本原因，不同key的map要存储到同一位置。那table的单个bucket中想要存放多个entry，显然不对，所以HashMap底层采用链表解决冲突

数组中存放的是Entry实体链表，如果产生hash冲突，就插入到链表中。根本解决了hash列表中能一个bucket存放多个entry的问题

也可以从另一方面分析：table定长后，就算不同的hash值，indexFor得到的index也可能相同。链表解决的就是这个问题。来到同一index的entry，key值一样的，hash必然也一样，也就是覆盖就行了。处理的就是那种不同key得到了相同的hashcode来到了同一index的entry，就要放到链表中。

总的理解hash冲突就是，不同key的数据要存到table的同一位置，核心问题就是不同keyhash值可能一样。

关于indexFor：

一般对哈希表求散列我们会使用hash值对length取模，HashTable就是这样实现的，这种方法可以保证元素在哈希表中散列均匀，但取模会用到除法运算，效率非常低，HashMap是对HashTable进行改进后的实现，为了提高效率，使用h&（length-1）取代除法运算，在保证散列均匀的基础上还保持了效率的提升

具体算法：hash & (length-1)，hash与上数组长度-1，等同于hash mod length

例：15%4=3，代替为 15 & 3=1111 & 0011=0011=3

HashMap的性能问题

知道了HashMap的存储结构，table+链表，比如存储相同的元素个数，table小了，hash冲突就多了，链表就长了。相反，table大了，hash冲突就少了，链表就短了。

负载因子（load factor）：

当创建 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子可以减少 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。

HashMap构造：

默认初始的加载容量是16，加载因子是0.75。

//hashmap实际允许的最大元素个数
threshold = (int)(capacity * loadFactor);

当容量超出此最大容量时， resize后的HashMap容量扩大2倍。

void addEntry(int hash, K key, V value, int bucketIndex) {  
    Entry<K,V> e = table[bucketIndex];  
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
    if (size++ >= threshold)  
        resize(2 * table.length);  
        
        ...
}

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);//用来将原先table的元素全部移到newTable里面
    table = newTable;  //再将newTable赋值给table
    threshold = (int)(newCapacity * loadFactor);//重新计算临界值
}

一旦涉及到扩容，是比较耗费性能的，涉及到两个列表数据的临时交换，所以，在实际开发中，根据实际map的数据量，初始化HashMap的时候指定初始容量和负载因子。HashMap有几种入参的构造方法，可以自行查看，一般开发中map数据也不会很大，指定初始化容量即可

注意：指定初始化容量，尽量是2的N次幂的数字，以降低重复率，不深入，可以看下这篇了解一下

成员变量 DEFAULT_INITIAL_CAPACITY 为什么是2的n次方

转红黑树

参考文章（原文：https://blog.csdn.net/xiewenfeng520/article/details/107119970）

红黑树查询时间复杂度是O(logn)，链表查询查询时间复杂度是O(n)。我们知道，put数据的key值是可以自己实现hashcode算法的，如果算法不好导致hash散列不那么均匀，可能会导致table中某bucket的链表很长的，所以，就导致了查询效率很低了。另外，虽然红黑树的查询效率高，但是采用treenode的数据结构占用的空间是链表的两倍。所以，性能和空间的折中，得到一个阈值，当链表长度达到8时，转为红黑树结构。

阈值为什么是8

原码给的有解释：具体一坨英文注释就不沾了，原码给了链表长度达到8的命中概率计算如下

//注释就不沾了

0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006

链表长度能达到8的概率极小，小于千万分之一。因为如果 hashCode 分布良好，也就是 hash 计算的结果离散好的话，很少出现链表很长的情况，这个8就这么定了。

总结：

通常如果 hash 算法正常的话，那么链表的长度也不会很长，那么红黑树也不会带来明显的查询时间上的优势，反而会增加空间负担。所以通常情况下，并没有必要转为红黑树，所以就选择了概率非常小，小于千万分之一概率，也就是长度为 8 的概率，把长度 8 作为转化的默认阈值。

所以如果平时开发中发现 HashMap 或是 ConcurrentHashMap 内部出现了红黑树的结构，这个时候往往就说明我们的哈希算法出了问题，需要留意是不是我们实现了效果不好的 hashCode 方法，并对此进行改进，以便减少冲突