jdk1.7hashMap源码分析
1.8的源码分析在这里：jdk1.8hashMap源码分析
jdk1.7的map接口结构：
jdk1.8的map接口结构：
hashMap继承关系：
hashTable继承结构：
concurrentHashMap继承关系：
哈哈，我比较懒，不想画图，自行脑补三者关系。
几个关键字说明：
//map 初始化容量，即数组大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//承载量=容量*加载因子
int threshold;
//加载因子
final float loadFactor;
//map结构变更过的次数
transient int modCount;
//声明的表，初始化为空
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// key-map键值对的个数，不能大于承载量
transient int size;Map<String,Object> param = new HashMap<>();new一个对象，我们看看hashmap做了什么:
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;//初始化加载因子
threshold = initialCapacity;//初始化承载量，16
init();//供子类扩展的方法
}可以看出，只初始化了加载因子和承载量。
下面分析，put() 和 remove方法。
put():
public V put(K key, V value) {
if (table == EMPTY_TABLE) {//初始化数组，容量为16
inflateTable(threshold);//初始化table数组，源码在下面
}
if (key == null)
return putForNullKey(value);//如果key为空，则
int hash = hash(key);//根据key求出hash值
int i = indexFor(hash, table.length);//求出在数组中的位置
for (HashMap.Entry<K,V> e = table[i]; e != null; e = e.next) {//遍历链表找出对应的key，覆盖原有的value
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//如果没找到，则新增一个Entry,结构改变，modCount加一
modCount++;
addEntry(hash, key, value, i);//源码解释在下面
return null;
}//取hash值得算法
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {//遍历链表，如果找到key值为null，将value赋值给对应的key
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//如果没找到，链表会增加一个节点，结构变化了，modCount加一
modCount++;
addEntry(0, null, value, 0);//添加一个key为null，值为value的Entry,源码向下看
return null;
}void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {//判断是不是需要扩容，扩容以后需要重新算hash值和数组下标位置
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);//源码向下看
}
createEntry(hash, key, value, bucketIndex);//源码向下看
}static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);//查找entry在数组中存放的位置
}void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];//bucketIndex位置值赋值给e
table[bucketIndex] = new Entry<>(hash, key, value, e);//new 一个Entry放在bucketIndex
size++;
}remove():
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}final HashMap.Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {//size表示hashmap中 HashMap.Entry对象的个数,如果为零，表示空map
return null;
}
int hash = (key == null) ? 0 : hash(key);//根据key求出hash值
int i = indexFor(hash, table.length);//求出元素在哪个数组位置
HashMap.Entry<K,V> prev = table[i];//取出对应的链表
HashMap.Entry<K,V> e = prev;//遍历用，存储遍历元素的前一个元素或者当前entry
while (e != null) {
HashMap.Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {//遍历链表，找到对应的key
modCount++;//找到对应的元素，map结构改变一次，modCount加一
size--;//HashMap.Entry对象的个数减一
if (prev == e)//如果当前entry就是要找的，直接将下一个entry放在数组对应位置，（要删除元素在链表头部）
table[i] = next;
else
prev.next = next;//从中间删除节点，直接让被删元素上一个entry指向它的下一个entry
e.recordRemoval(this);//这个不知道干嘛的
return e;
}
//如果当前节点不是要找的元素，继续遍历链表
prev = e;
e = next;
}
return e;
}private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);//初始化容量，默认为16
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//初始化承载量
table = new Entry[capacity];//初始化table数组
initHashSeedAsNeeded(capacity);//这个暂时不做解释
}private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;//初始化table容量，保证容量是2的幂次
}//扩容 当元素数量>=承载量时，进行扩容
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {//容量为2的幂次，最大为2的30次方，所以一直扩容肯定有等于最大幂次的时候
threshold = Integer.MAX_VALUE;//这时就把Integer的最大值给承载量
return;
}
Entry[] newTable = new Entry[newCapacity];//创建新的table
transfer(newTable, initHashSeedAsNeeded(newCapacity));//判断新的table中的元素是否需要重新求hash值，源码在下面
table = newTable;//数组扩容赋值给table
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//算出新的承载量
}void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {// 遍历旧表，如果需要重新求hash值就进行rehash操作
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}//这段没看懂，大体意思是初始化好数据，如果需要则作为是否进行rehash的条件
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}所以，1.7和1.8的hashmap到底有哪些不同呢： 1.hash的取值算法不同 2.求数组下标的算法不同 3.1.8的实体是Node继承了entry，链表长度大于8的时候转换为红黑树。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018/10/19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读