基本介绍
其实HashMap底层是个什么东西我们之前也讲过, 就是一个哈希桶(差不多可以看成一个数组), 然后每一个节点又连接着链表/红黑树之类的, 下面让我们看一看具体在源码上是怎样实现的:
常量及其它
-> static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//这个指代的是哈希桶的大小, 默认为16
-> static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默认的负载因子 -> 0.75
-> static final int TREEIFY_THRESHOLD = 8;
//树化的条件之一, 就是指当一个节点上的链表长度大于8时(也不一定是8, 但跟8是有关的, 后面讲put的时候再说),就会从链表转换为红黑树
-> static final int MIN_TREEIFY_CAPACITY = 64;
//树化的条件之一, 就是指当哈希桶的大小如果大于64(数组的长度), 就会将链表转换成红黑树
-> static final int UNTREEIFY_THRESHOLD = 6;
//解树化的条件, 当红黑树的大小小于8时, 就会从红黑树转换回链表.
-> static class Node<K, V> implements Map.Entry<K, V> {...
这段代码定义了一个静态内部类'Node', 该类实现了'Map.Entry<K, V>'接口, 表示哈希表中的一个节点, 用于存储键值对.
构造方法
含指定容量, 负载因子的
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;
this.threshold = tableSizeFor(initialCapacity);
}
这个是提供了指定容量, 负载因子的, 玩家可以自行设置这两个参数. 需要注意的是在:
if(initialCapacity > MAXIMUM_CAPACITY) {}
这个中, MAXIMUM_CAPACITY是指1>>30, 也就是说当玩家设置的值大于这个值之后, 就会被设置为这个值(显而易见, 为了防止移除)
含指定容量的
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
这个很好理解, 就是当不给负载因子时, 就是默认的0.75, 然后通过this()调用上面的构造方法.
俺一无所有
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
这个就比较令人匪夷所思了, 它只有默认的负载因子(当然,还是0.75). 然后奇怪的是它居然没有给设置容量! 没事, 让子弹飞一会.
put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
让我们先来看一下里面的hash()方法.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这里采用了将key的hashCode()值与h右移 16位取异或得到哈希值.
这种位操作目的是将hashCode()返回的高位和低位进行混合, 增加哈希值的随机性和分布性, 从而减少哈希冲突的概率.
再来看一下putVal()方法.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
不难发现在4, 5行中,
if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;我们发现当这个传来的哈希标为空/或者大小为0时, 会让表调用resize().
这里是resize()中的部分内容:
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;通过这个, 我们就可以得出结论, 在第一次put的时候, 哈希桶大小分配为了默认的newCap(其实是16).
继续分析putVal()方法中的剩余部分.
if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);在这里, 就是哈希表中插入新键值对的逻辑(就是哈希桶这个位置为空), 通过(n - 1) & hash的方式映射到数组索引i上, 这是因为 'n'应该是2的幂次方(即哈希表长度应该是2的幂次方), 才能保证哈希值均匀分布. 然后调用newNode完成了插入操作.
p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break;当需要插到链表/红黑树上时, 就需要通过尾插法插入, 在这里, 我们发现, 当链表长度大于 8 - 1时, 就会通过treeifyBin方法进行树化.
那么到这里就讲完了(我讲的是比较爱考的), 其它部分如果感兴趣的话希望你们自己看看源码推理推理.
下了...