Java基础 (23) HashMap

1）HashMap的实现原理
2）ConcurrentHashMap的实现原理
3）TreeMap 具体实现
4）LinkedHashMap

数据结构中有数组和链表来实现对数据的存储，但这两者基本上是两个极端。

在HashMap(Java 8以前)：数组+链表

在HashMap(Java 8 及以后)：数组+链表+红黑树

resize方法中的元素为Node。

HashMap：put方法逻辑
1、如果HashMap未被初始化过，初始化
2、对Key求Hash值，然后再计算下标
3、如果没有碰撞，直接放入桶中
4、如果碰撞了，以链表的方式链接到后面
5、如果链表长度超过阈值，就把链表转成红黑树
6、如果链表长度低于6，就把红黑树转会链表
7、如果节点已经存在了就替换旧值
8、如果桶满了（容量16*加载因子0.75），就需要resize（扩容2倍后重排）

HashMap：从获取hash到散列的过程。

扩容问题

• 多线程环境下，调整大小会存在条件竞争，容易造成死锁
• rehashing 是一个比较耗时的过程

HashMap总结

• 成员变量：数据结构，树化阈值
• 构造函数：延迟构建
• put和get的流程
• 哈希算法，扩容，性能

同步方式

如何优化HashTable？

• 通过锁细粒度化，将整锁拆解成多个锁进行优化

  
  
  
  ConcurrentHashMap