存储

  • 数组存储
  • 通过 key-value 键值对分散存储在一个数组中，key 通过 hash 运算转化为数组下标

put()

alt


时间复杂度：

alt


多线程情况下，put()可能导致多线程数据被覆盖

  • A线程执行put方法存储数据，首先通过hash函数计算索引下标，然后获取到该下标里面的链表头节点，此时A线程的时间片用完了；
  • B线程执行，计算出的索引下标跟A线程的一致，成功执行之后；
  • A线程再次执行，依然持有过期的链表头，以至于覆盖了线程B插入的记录；导致B线程的数据被覆盖。


扩容

公式

  • 阈值 = capacity（容量） * loadFactor（加载因子）
  • 默认情况下，capacity = 16、loadFactor = 0.75f，所以阈值默认为 12
  • 当元素达到阈值就会触发扩容、每次扩容的容量是之前的2倍

构造函数

  • hashmap 并不会直接采用我们传入的数值，而是会采用第一个大于该数值的2的幂作为初始化容量。目的是提高hash效率
  • 通过 tableSizeFor() 获得初始容量
static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

传入的new HashMap<>(100)，在这期间会发生扩容嘛？

  • 实际容量经过tableSizeFor() 计算得到128，也就是阈值为96，会再次发生扩容。

  • 但是，这样计算的阈值不是我们期望的，因为在元素达到96的时候会发生扩容；所以《阿里巴巴java开发手册》建议： alt

  • 这样我们需要100个元素，按照公式计算需要传入133个元素，通过计算的实际初始化容量为256，从而阈值为192。

  • 这样会牺牲些内存但是可以有效的减少冲突，也可以避免rehash的过程消耗的时间。


为什么每次 resize() 都是 capacity 的2倍

比如：16的二进制表示为 10000，那么 length - 1 就是 15，二进制为 01111，同理扩容后的数组长度为 32，二进制表示为 100000，length - 1 为 31，二进制表示为 011111。

  • index（put 操作不容易碰撞）：因为计算 index 时用的是（n-1） & hash，这样就能保证 n - 1是全为1的二进制数。如果不全为1的话，存在某一位为0，那么0与任何的结果都是0，这样便有可能将两个hash不同的值最终装入同一个桶中，造成冲突。所以必须是2的幂。
  • resize（减少了 resize 之前已经散列良好的老数组的数据位置重新调换）：HashMap的数组长度一定保持2的次幂，这样会保证低位全为1，而扩容后只有一位差异，也就是多出了最左位的1，这样在通过 hash&(length-1)（计算新下标）的时候，只要h对应的最左边的那一个差异位为0，就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换)，个人理解。

为什么负载因子 LoadFactor = 0.75

  • 负载因子0.75是对空间和时间效率的一个平衡选择
  • 如果内存空间很多而又对时间效率要求很高，可以降低负载因子Loadfactor的值
  • 如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1

扩容后下标的位置

  • 正常情况下，计算节点在table中的下标的方法是：hash&(oldTable.length-1)，扩容之后，table长度翻倍，计算table下标的方法是hash&(newTable.length-1)，也就是hash&(oldTable.length*2-1)
  • 于是我们有了这样的结论：这新旧两次计算下标的结果，要不然就相同，要不然就是新下标等于旧下标加上旧数组的长度。

alt


为什么还需要使用 (h = key.hashCode()) ^ (h >>> 16) 计算hash值？

  • 已经可以通过 hash&(oldTable.length-1) 计算出 hash值，为什么还需要将 key.hashcode与其hashcode右移16位的异或结果作为 hash值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • 由于最终获取下标是对二进制数组最后几位的与操作（map长度大部分时候较小）。所以直接取hash值会丢失高位的数据，从而增大冲突引起的可能。
  • 由于hash值是32位的二进制数。将高位的16位于低位的16位进行异或操作，即可将高位的信息存储到低位。因此该函数也叫做扰乱函数
  • 目的就是减少冲突出现的可能性。而官方给出的测试报告也验证了这一点。直接使用key的hash算法与扰乱函数的hash算法冲突概率相差10%左右。

多线程下 get() 可能因为 resize() 导致死循环

  • 使用头插法将原链表更新到新数组的对应位置，会导致链表翻转，可能会产生死循环；
  • A线程执行扩容原数组里面一个链1-2-3，定位到1的时候，时间片用完；
  • B线程执行扩容，并完成，根据头插法，对应的链路可能是3-2-1；
  • A线程再次执行，持有的是被B线程扩容的数据，会将1节点插入到对应位置上，这就造成了3-2-1-3环形链表；
  • 所以在get 的时候就会陷入死循环。

补充：

  • 1.8 使用尾插法进行插入，可以保证数据的有序性，避免了死循环


Hash 冲突

链表法（ThreadLocal）

  • 引入链表结构解决冲突，发生冲突会数组下标对应的位置进行尾插

缺点：

  1. 内存不连续对 CPU 缓存不友好
  2. 存储小对象的时候，由于还要存储指针会消耗内存
  3. 极端情况下，会引入红黑树代替链表，解决链表查询深度问题，时间复杂度为：O(logn)

为什么先用链表而不是红黑树？

  • 红黑树属于二叉平衡树，在插入新数据可能会通过左旋、右旋、变色等操作维护平衡，需要付出代价。当维护平衡二叉树所消耗的资源与遍历线性链表少的时候才会选择红黑树
  • 红黑树的引用时为了解决链表查询的深度问题，开始的时候也就是 <= 8 的时候、深度小、使用链表反而会更快一些

什么时候红黑树退化成链表？

  • 红黑树节点数 <= 6 的时候退化成链表
  • 如果红黑树根节点为 null、根节点的左子树或者右子树为 null、根节点的左子树的左子树为 null 都会发生退化

为什么红黑树与链表相互转化的阈值不同？

  • 链表转化为红黑树，节点数 >= 8 并且 容量 > 64
  • 如果节点数 >= 8 但是容量 < 64 则先进行扩容，达到 64 之后再进行树化
  • 红黑树转化为链表，节点数 <= 6

阈值不同是为了作为缓冲，可以有效防止链表和红黑树之间频繁转换


开放寻址法（ThreadLocal）

  • 一旦发生了冲突，就去寻找下一个空的散列表

优点：

  1. 散列表中的数据都存储在数组里，可以有效的利用 CPU 缓存加快查询速度
  2. 序列化容易，不涉及链表的指针结构

缺点：

  1. 删除数据需要特殊标记已经删掉的数据，不能标记为 null，因为查询的时候，通过 hash 函数找到的下标不匹配会依次遍历到 null 截止会返回没有找到
  2. 装载因子太大会造成空闲位置少，冲突频繁

应用：



线程安全

HashTable

  • HashTable同步、在若干方法都添加了synchronized关键字，也就意味着线程安全
  • hashmap的key和value都允许为null，而hashtable不允许
  • 参考：synchronized

currentHashMap

  1. JDK1.7使用分割分段，通过Reentrantlock + segment数组 + hashEntry数组 + 链表。
  2. JDK1.8使用node数组，通过node数组 + synchronized + cas + 链表 + 红黑树。

优势在于降低了锁的粒度，原1.7的粒度基于segement包含多个hashEntry，而1.8对的粒度基 hashEntry。使用红黑树优化链表。



有序性

  • 由于hashmap存储是无序，所以为了保证遍历map的时候，元素时按照先后排序的得使用linkedHashMap、TreeMap

LinkedHashMap

  • 多加了一条双向链表保证了元素的遍历顺序

alt


根据构造函数，可以指定双向链表的顺序排序

  • 插入排序：默认 accessOrder = false
  • 访问排序：accessOrder = true，可以用来实现LRU算法（最近最久未使用，常用于页面置换算法）

补充：

  • LRU算法，时间复杂度为：O（1）
  • 使用哈希表存储数据，查找的时间复杂度为O（1）
  • 使用双向链表进行数据的插入、删除等操作，时间复杂度为O（1）
  • 146. LRU 缓存

TreeMap

  • TreeMap基于红黑树实现。查找、删除、插入的时间复杂度都是O(logn)。
  • TreeMap实现了SortedMap接口，保证了有序性。默认的排序是根据key值进行升序排序，也可以重写comparator方法根据value进行排序具体取决于使用的构造方法
  • 不允许有null值、null键。
  • 线程不安全。

红黑树

  1. 每个节点非黑即红
  2. 根节点总是黑色的
  3. 红节点周围必须是黑节点（反之不成立）
  4. 叶子节点都是黑色的空节点（NIL节点），也就是说叶子节点其实都是null
  5. 从根节点到任意一个叶子节点锁经历的黑色节点都相同（相同的黑色高度）


参考