# HashMap实现原理

HashMap是常考点，而一般不问List的几个实现类(偏简单)。以下基于JDK1.8.0_102分析。

JDK版本：oracle java 1.8.0_102

# 内部存储

HashMap的内部存储是一个数组（bucket），数组的元素Node实现了是Map.Entry接口(hash, key, value, next)，next非空时指向定位相同的另一个Entry，如图：

Tips:

• 如果数据增长很快的话，或数据规模可预知，可以在创建HashMap时主动设置capacity

# hash与定位

## hash方法的实现和定位

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

## 碰撞

• 覆写后，一定要保证equals判断相等的时候，hashCode的返回值也相等
• 对于选作key的类，要保证调用put与get时hashCode的返回值相等，equals的性质相同

# resize

resize是HashMap中最难理解的部分

Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.

• 全部
• 标签
• 友链