java hashmap 问题汇总

红太狼 2023-05-29 06:15 7阅读 0赞

### 如何保证hashmap 数组大小一定是2的指数 ###

tableSizeFor 在初始化 hashmap对象时会调用来得到这么一个值，这个值用来作为hashmap 数组大小。

static final int tableSizeFor(int cap) {
            int n = cap - 1;
            n |= n >>> 1;    //  无符号 右移 1位，|  符号是 或 操作，一直将后面 的地位全部置1
            n |= n >>> 2;    //  无符号 右移 2位
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

这段代码可以将cap 变成一个2的指数，cap化成二进制后，高位后一位变成1，低位全部变成0，这样得到一个2的指数代表的容量。

拿数字 5 做例子： 5： 0101

*  n = cap - 1 ： n = 4 :0100
 *  n |= n >>> 1 ： 0100 | 0010 = 0110
 *  n |= n >>> 2：0110 | 0001 = 0111
 *  后面几个操作也是这样，那么 n = 0111 + 1 = 1000 = 8

for (int i = 0; i < 7; i++) {
                System.out.println(tableSizeFor(i));
            }

输出结果：

1
    1
    2
    4
    4
    8
    8

大家可以操作一下。

### 为什么表大小一定是2的倍数？ ###

我们来看下表长是7，用于取模运算的时候要减去1，也就是7-1 = 6 ，二进制是 0110 ，左高位，右低位，右边第1位是0，所有数字与它做与运算都是0，不利于均匀散列，而8这个数字，8-1 =7 ，二进制是0111，低位都是1，这样其他数字跟他 与 运算，0&1=0，1&1=1，比较均衡，那为啥减1取模？数组坐标是从0开始的，所以长度为8的数组，坐标范围是0到7。扩容都是2倍扩容，总不能3倍扩容，4倍扩容，太浪费空间了，所以综合初始大小、扩容倍数可以知道表大小一定是2的倍数。同时这么做有几点好处：

*  降低碰裂次数，散列更均衡
 *  避免空间不被浪费利用，其实还是散列问题，散列不好，很多空间都没有数据，不久浪费了。

### 为什么初始大小是16？ ###

这个问题 首先考虑的就是 为什么不是 8 、32 ？

*  8太小了，很容易导致map扩容影响性能
 *  32太大了，又会浪费资源

这里的选取主要会考虑：

*  减少hash碰撞
 *  提高map查询效率
 *  分配过小会造成频繁扩容
 *  分配过大浪费资源

### 扩容阈值 ###

扩容阈值 = 容量 x 加载因子。  
扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量）， 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。扩容都是2倍的扩容。

### jdk 7 与 jdk 8 不同点 ###

*  红黑树  
    当链表特别长的时候，查找效率降低了，jdk8引入 红黑树，提高查找速度
 *  hash碰撞时  
    jdk8 先判断是红黑树，是红黑树插入树中，不是红黑树插入链尾
 *  rehash 顺序不一样  
    jdk7 逆序扩容，jdk 8 顺序扩容，保证不会出现闭环情况，这个单独讲解。

### 多线程的循环引用情况 ###

hashmap不是线程安全的，在多线程环境下会出现循环引用情况，我们分析一下，有A、B两个线程，他们都插入数据钱发现要执行扩容，当前情况是有一个数组链表是entry 1，下一个entry 是 entry 2，开始表演：

*  1、线程A进来，拿到了entry 1 ，next 是 entry 2，暂停
 *  2、线程B进来，拿到了entry 1，开始扩容，jdk 7 扩容是逆序，扩容后是entry 2 - - > entry 1。
 *  3、线程A 醒来了，还是指向entry 1 ，进行扩容，hash后还是这个表index，插入表头，由于entry 2已经在了，所以entry 1指向entry 2
 *  4、然后next 节点晋升当前节点，也就是entry 2，next指向entry 2的下一个节点，由于线程B的缘故，entry 2的下一个节点是entry 1，所以next为entry 1，
 *  5、entry 2 插入到表头，指向entry 1，entry 1 在第3步骤中已经指向了entry 2，所以开始了无限循环。

形成循环引用的原因是表头插入，这样扩容的时候，从表头到表尾取数据，rehash到新的数组坐标下，做表头插入，这样扩容后的顺序是扩容前的逆序，jdk 1.8对此做了优化，每次都是表尾插入，这样顺序跟之前还是一样的。

### 为什么连表大小为8的时候就转换为红黑树 ###

链表长度达到8就转成红黑树，当长度降到6就转成普通bin，有的资料说因为查找效率，因为：

*  红黑树 时间复杂度是： l o g ( n ) log(n) log(n) ， n=8 时 时间复杂度是3。
 *  链表时间复杂度： n 2 \\frac\{n\}\{2\} 2n，n=8时，时间复杂度是4。

不过这里有一点，我看了jdk 1.8的链表代码，他是for循环的，for循环的时间复杂度就是 O ( n ) O(n) O(n)，不知道为啥在这里就变成 O ( n 2 ) O(\\frac\{n\}\{2\}) O(2n)，估计很多作者在这里理解时用所谓 的平均复杂度来做计算，但实质是平均复杂度的计算没有那么简单，这还跟概率有关，具体可以参考：[复杂度分析（下）：浅析最好，最坏，平均，均摊时间复][Link 1]、[数据结构-最好、最坏、平均时间复杂度的分析（笔记2）  
][-_2_]。  
所以这个说法不是最终的原因，书中源码这么说：

Because TreeNodes are about twice the size of regular nodes, we
    use them only when bins contain enough nodes to warrant use
    (see TREEIFY_THRESHOLD). And when they become too small (due to
    removal or resizing) they are converted back to plain bins.  In
    usages with well-distributed user hashCodes, tree bins are
    rarely used.  Ideally, under random hashCodes, the frequency of
    nodes in bins follows a Poisson distribution
    (http://en.wikipedia.org/wiki/Poisson_distribution) with a
    parameter of about 0.5 on average for the default resizing
    threshold of 0.75, although with a large variance because of
    resizing granularity. Ignoring variance, the expected
    occurrences of list size k are (exp(-0.5)*pow(0.5, k)/factorial(k)). 
    The first values are:
    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
    more: less than 1 in ten million

理想情况下使用随机的哈希码，容器中节点分布在hash桶中的频率遵循泊松分布(具体可以查看http://en.wikipedia.org/wiki/Poisson\_distribution)，按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表，可以看到链表中元素个数为8时的概率已经非常小，再多的就更少了，所以原作者在选择链表元素个数时选择了8，是根据概率统计而选择的。

hash算法足够好，也就是碰撞低，从而hash分布遵循泊松分布，那么这样，一个链表中冲突有8个的概率就是0.00000006，非常低，几乎是不太可能的，所以 hash算法不好的话，冲突就非常多，多余8个就为了提高效率换成红黑树。

### ConcurrentHashMap ###

volatile 修饰，保证了可见性。  
1.7使用分段锁，采用了ReentrantLock锁机制来保证，ReentrantLock，一个可重入的互斥锁，它具有与使用synchronized方法和语句所访问的隐式监视器锁相同的一些基本行为和语义，但功能更强大。  
分段锁更多的类似二维数组，行表示segment数组，列表示hashEntry数组。segment对象直接继承ReentrantLock。  
1.8使用了 CAS + synchronized 来保证并发安全性。

#### 1、用 HashEntery 对象的不变性来降低读操作对加锁的需求 ####

在代码清单“HashEntry 类的定义”中我们可以看到，HashEntry 中的 key，hash，next 都声明为 final 型。这意味着，不能把节点添加到链接的中间和尾部，也不能在链接的中间和尾部删除节点。这个特性可以保证：在访问某个节点时，这个节点之后的链接不会被改变。这个特性可以大大降低处理链表时的复杂性。

#### 2、用 Volatile 变量协调读写线程间的内存可见性 ####

volatile 型变量 count ，特性和前面介绍的 HashEntry 对象的不变性相结合，使得在 ConcurrentHashMap 中，读线程在读取散列表时，基本不需要加锁就能成功获得需要的值。这两个特性相配合，不仅减少了请求同一个锁的频率（读操作一般不需要加锁就能够成功获得值），也减少了持有同一个锁的时间（只有读到 value 域的值为 null 时 , 读线程才需要加锁后重读）。

### 参考博客 ###

[Link 1]: https://www.jianshu.com/p/f985d18489f7
[-_2_]: https://zhuanlan.zhihu.com/p/65492200