1、HashMap

1 计算hash桶位置公式的好处

  1. // 1 计算hash桶位置的公式
  2.     (n - 1) & hash // 这个公式的作用是为了计算出hash值所处的桶位置，其实就是 hash % n. 
  3.     // 好处是位运算效率更高
  4.     // 但是有个条件就是 n必须是2^n，因为只有这n = 2^n时，(n - 1) $ hash == hash % n
  5. // 2 hash 的计算方法
  6.     static final int hash(Object key) {
  7.         int h;
  8.         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  9.         // 将hash值的低16位，异或 hash值的高16位，得到一个新的hash值
  10.     }
  11.     为了让hash值的每一位都能影响结果，能够起到减少hash冲突的作用

2 put方法逻辑

  1. public V put(K key, V value) {
  2.       return putVal(hash(key), key, value, false, true);
  3. }
  4. final V putVal( int hash, K key, V value, boolean onlyIfAbsent, boolean evict){
  5.     // 1 判断 table == null || table.length == 0
  6.        // true:  调用resize()
  7.     //2 判断目标hash位置是否为null
  8.        // true: 当前位置还没有元素，新建Node节点直接插入目标位置
  9.              if ((p = tab[i = (n - 1) & hash]) == null)
  10.              tab[i] = newNode(hash, key, value, null);
  11.        //false: 当前位置已有元素
  12.        // 3 将元素插入到桶中
  13.        // 3.1 if 如果 插入的元素 等于桶的第一个元素 则什么都不干
  14.        // 3.2 else if 如果桶第一个元素类型是 TreeNode 则调用putTreeVal将元素插入到红黑树
  15.        // 3.3 else 将元素插入到链表尾部， 插入后需要判断是否链表的长度是否 >= 树化阈值， 大于则将链表树化。 循环过程中如果判断key是否存在，若存在更新当前节点为最新。
  16.     // 4 根据 onlyIfAbsent  判断是否更新 value值  
  17. }
  • 判断table是否为空,如果为空则初始化

  • 根据当前key的hashcode定位到具体桶，并判断是否为空，为空则表示无hash冲突则直接创建node并插入桶中

    • 如果当前桶有值（hash冲突），那么就比较当前桶位置hash和key 都与 要插入的hash和key相同，则当前节点直接赋值给e

    • 3 get方法(1.8)

  • 将key hash之后取得所定位得桶

  • 如果桶为空则直接返回null
  • 否则判断桶得第一个位置得key是否为查询得key，是就直接返回value。
  • 如果第一个不匹配，则判断它得下一个是红黑树还是链表。
  • 红黑树就按照树得查找方式返回值
  • 不然就按照链表得方式遍历匹配返回值

    从两个核心方法(get/put)可以看出1.8对大链表做了优化，修改为红黑树之后查询直接提高到了o(logn)

4 HashMap 1.7和1.8有何变化

1、ConcurrentHashMap

1.7版本

segment 数组 + 链表 组成
concurrentHashMap采用分段锁技术，其中Segment继承于ReentrantLock。 当一个线程占用锁访问一个segment的时候，不影响其他segment。
**

  1. 首先会尝试获取锁，如果获取失败则自旋获取锁，若自旋重试次数达到阈值，则改为阻塞锁获取。

get逻辑比较简单，只需要将key通过hash之后定位到具体的segment，再通过一次hash定位到具体的元素上。 HashEntry 中的value是用valatile关键字修饰的，保证了内存可见性。每次获取都是最新值。

1.8版本优化

抛弃了原有的segment分段锁，而是采用了 CAS + synchroinzed 保证并发安全性
跟HashMap很像，也把之前的HashEntry改成了Node，但是作用不变，把值和next采用volatile去修饰，保证了可见性，并且引入了红黑树。
值的存取过程？以及如何保证线程安全？
concurrentHashMap 在进行put操作

  1. 根据key计算出 hashcode
  2. 判断是否需要进行初始化
  3. f 即为当前key定位出的Node，如果为空表示当前位置可以写入数据，利用CAS尝试写入，失败则自旋保证成功
  4. 如果当前位置的hashcode = MOVED = -1 ,则需要扩容。
  5. 如果都不满足，则利用synchroinzed锁写入数据。
  6. 如果数量大于 TREEIFT_THRESHOLD 则需要转为红黑树

concurrentHashMap的get操作

  1. 根据计算出来的hashcode寻址，如果在桶上那么就直接返回。
  2. 如果是红黑树那就按照树的方式获取值
  3. 不满足就按照链表的方式遍历获取值

    1.8在1.7的数据接口上做了大的改动，采用红黑树之后可以保证查询效率o(logn),甚至取消了ReentrantLock改为synchronized，