集合-HashMap解析
2017-09-15 本文已影响0人
史云龙
一、概述
- HashMap的底层数据结构是数组，但是数组中存放的并不是一个对象而是链表。所以也可以成HashMap的数据结构是哈希桶。在JDK1.8中如果链表存放的元素超过8个就将链表转换成红黑树。为了保证元素冲突时，查询和插入效率。Andro中则一直是链表。数组每一位存储的是链表的头部。链表的使用时基于哈希表解决冲突(碰撞)使用的方法：链地址法
- HashMap默认数组长度(Android：2然后在第一次增加数据后就变成了4，Java：16)，默认扩容长度为原来数组长度的一半，数组长度也称容量。在数组内元素超过阈时，就会进行扩容。阈=负载系数数组长度。负载系数可以自定义也可以使用默认值0.75*;
- 关于hash计算：通过使用key的hashCode()，然后经过哈希函数将hashCode转换为相应哈希值，通过位运算来计算应该放在表中的哪个位置，位运算效率高于取模运算。哈希函数尽量使得数据的分布均匀。HashMap的Key对象尽量需要复写父类的hashCode()和equals()方法，这两个方法主要用于HashMap中存储。
其中hashCode用于hash值及表中位置的位运算。equals用于判断key值是否相等。 - 关于扩容以及扩容后的数据位置转换。首先判断是否需要扩容。需要扩容，那么容量变为原来的两倍。扩容后数据需要判断是否需要向数组的高位移动，判断方式是元素的hash值与上数组原来的长度(hash&oldCap)，如果不为0就需要向高位移动。高位的位置是现在的位置加上oldCap(原来的数组长度)。
- HashMap中重要的两个参数是容量(Capacity)和负载系数(Load factor)。其中容量是指桶的数目，负载系数是在桶填满程度的最大比例。这两个参数关系到了哈希表的性能。Android中负载因子没有用。。。
二、构造函数及节点信息
2.1 构造函数
关键字transient表示实现接口Serializable的对象字段不能被自动序列化
Java
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//默认初始化容量，16
static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量：2的30次方
static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认负载系数：0.75
transient Node<K,V>[] table;//表，Node数组
transient Set<Map.Entry<K,V>> entrySet;//Map的Entry
transient int size;//大小
transient int modCount;//修改次数
int threshold;//阈，负载系数*容量
final float loadFactor;//负载系数，可自定义
//自定义初始化容量和负载系数的构造函数
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)//如果初始化容量小于0，抛出异常
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)//如果初始化容量大于最大容量，那么将初始化容量设为最大容量
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))//负载系数小于0或者是空
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;//设置负载系数
this.threshold = tableSizeFor(initialCapacity);//设置阈，在第一次put的时候将表的容量设为当前的阈值，并重新修改阈值
}
//只有初始化容量的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//默认构造函数，只是将负载因子设为默认参数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//参数是Map的构造参数
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;//设置负载因子，为默认因子
putMapEntries(m, false);//将map的数据插入进去
}
//将cap的所有除最高位外变为1，然后+1，这样就变成了大于等于cap的2的n次方
static final int tableSizeFor(int cap) {
int n = cap - 1;//减1，方便处理最高位的值，假定最高位为m，最高位指的是int的二进制表示最高(第一个)1出现的位置，如果这个值的二进制是m位为1，而其他位为0的情况，类似与(10000=16)，就是2的n次方。
n |= n >>> 1;//将m-1位置处理为1
n |= n >>> 2;//将m-1到m-4位置处理为1
n |= n >>> 4;//将m-1到m-8位置处理为1
n |= n >>> 8;//将m-1到m-16位置处理为1
n |= n >>> 16;//将m-1到m-32位置处理为1
//其实就是将最高位外全部处理为1，具体参考下图演示的0，15，16，17
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
位运算
Android
private static final int MINIMUM_CAPACITY = 4;//最小的数组长度
private static final int MAXIMUM_CAPACITY = 1 << 30;
private static final Entry[] EMPTY_TABLE
= new HashMapEntry[MINIMUM_CAPACITY >>> 1];//空数组，长度为2
static final float DEFAULT_LOAD_FACTOR = .75F;//默认的负载因子
transient HashMapEntry<K, V>[] table;//表，使用HashMapEntry的表
transient HashMapEntry<K, V> entryForNullKey;//专门存储null键的键值对对象
transient int size;//size
transient int modCount;//修改次数
private transient int threshold;//阈
private transient Set<K> keySet;//key的集合
private transient Set<Entry<K, V>> entrySet;//entry的集合
private transient Collection<V> values;//值的集合
public HashMap() {//默认构造函数
table = (HashMapEntry<K, V>[]) EMPTY_TABLE;//将table设置空数组
//阈，在第一次增加元素的时候会进行数组扩容，数组长度也就变成了4
threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}
//设置初始容量的构造函数
public HashMap(int capacity) {
if (capacity < 0) {//如果容量小于0，抛出异常
throw new IllegalArgumentException("Capacity: " + capacity);
}
if (capacity == 0) {//如果容量为0
@SuppressWarnings("unchecked")
HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE;
table = tab;//将table设为空数组
threshold = -1; // Forces first put() to replace EMPTY_TABLE，阈值设为-1，为了第一次增加数据时扩容
return;
}
//容量小于最小容量，就将容量设置最小容量
if (capacity < MINIMUM_CAPACITY) {
capacity = MINIMUM_CAPACITY;
} else if (capacity > MAXIMUM_CAPACITY) {//容量大于最大容量，就设为最大容量
capacity = MAXIMUM_CAPACITY;
} else {//变成2的n次方
capacity = Collections.roundUpToPowerOfTwo(capacity);
}
//创建数组，阈值为数组的0.75
makeTable(capacity);
}
//设置初始容量，负载因子没有用
public HashMap(int capacity, float loadFactor) {
this(capacity);//调用容量函数，负载因子并没有用，只是为了符合java的构造方法
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Load factor: " + loadFactor);
}
}
//Map的数组
public HashMap(Map<? extends K, ? extends V> map) {
this(capacityForInitSize(map.size()));//调用容量相关的构造函数
constructorPutAll(map);
}
//使用容量，制造数组
private HashMapEntry<K, V>[] makeTable(int newCapacity) {
@SuppressWarnings("unchecked")
HashMapEntry<K, V>[] newTable
= (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity];
table = newTable;//将数组设为新创建的数组
//调整阈值
threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
return newTable;
}
static int capacityForInitSize(int size) {
//将size扩容一半
int result = (size >> 1) + size; // Multiply by 3/2 to allow for growth
//~(MAXIMUM_CAPACITY-1)=1<<31 + 1<<30
// (result & ~(MAXIMUM_CAPACITY-1))==0 ，true表示小于1<<30
// boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY
return (result & ~(MAXIMUM_CAPACITY-1))==0 ? result : MAXIMUM_CAPACITY;
}
Collections.java
//具体的算法，和Java中相同
public static int roundUpToPowerOfTwo(int i) {
i--; // If input is a power of two, shift its high-order bit right.
// "Smear" the high-order bit all the way to the right.
i |= i >>> 1;
i |= i >>> 2;
i |= i >>> 4;
i |= i >>> 8;
i |= i >>> 16;
return i + 1;
}
2.2 节点对象
Java
Java在1.8中有两种Node节点：普通Node(用于桶的链表)和树的Node(用于红黑树节点)
TreeNode的节点继承自普通Node(在JDK1.8中实际是孙子)。
普通Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//哈希值
final K key;//Key
V value;//值
Node<K,V> next;//下一个节点
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
//获取Key
public final K getKey() { return key; }
public final V getValue() { return value; }//获取值
public final String toString() { return key + "=" + value; }//转换成字符串
public final int hashCode() {//哈希值
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
//设置值
public final V setValue(V newValue) {
V oldValue = value;//老值
value = newValue;//值设置为新值
return oldValue;//返回老值
}
//判断是否相等
public final boolean equals(Object o) {
if (o == this)//是否相等
return true;
if (o instanceof Map.Entry) {//判断对象是否是Map的键值对
Map.Entry<?,?> e = (Map.Entry<?,?>)o;//将对象转换成相应的对象
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;//key和值相等，键值对相等。
}
return false;
}
}
红黑树的Node
这个红黑树使用Hash值进行比较，如果Hash相同，那么再使用key值进行比较。key值需要比较功能。
红黑树的增加删除需要平衡树，关于红黑树，参考链接内的内容。
红黑树的根节点放入哈希表中。
关于节点为啥不讲红黑树节点：因为也没太看懂Java代码。这里的红黑树表现会比较复杂。
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
Android
HashMap条目，链表的节点
static class HashMapEntry<K, V> implements Entry<K, V> {
final K key;
V value;
final int hash;//哈希值
HashMapEntry<K, V> next;//下一个节点
HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
}
public final K getKey() {//获取Key
return key;
}
public final V getValue() {//获取值
return value;
}
public final V setValue(V value) {//设置值
V oldValue = this.value;
this.value = value;
return oldValue;
}
@Override
public final boolean equals(Object o) {//判断是否相等
if (!(o instanceof Entry)) {
return false;
}
Entry<?, ?> e = (Entry<?, ?>) o;//key和value相等，那么Entry相等
return Objects.equal(e.getKey(), key)
&& Objects.equal(e.getValue(), value);
}
@Override public final int hashCode() {//哈希值
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
@Override public final String toString() {//转换成字符串
return key + "=" + value;
}
}
三、增加元素
3.1 增一个元素：增加一个键值对
将一个元素放入哈希表
Java
public V put(K key, V value) {
//根据key的hashCode()，求出key的哈希值。
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果tab是空，或者tab的长度为0，需要扩容
//默认构造函数创建的table就是空
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//tab重新设置大小，并将长度赋值
if ((p = tab[i = (n - 1) & hash]) == null)//计算key对应hash位置是否为空
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;//哈希值、key相等表示放入的键值对需要修改
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向后移动，直到p.next空
p.next = newNode(hash, key, value, null);//将p的后节点指向新创建的节点
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);//如果count=7，表示插入之后达到了8个，将数据结构换成链表
break;
}//如果值相等，打断循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}//如果e不为空，表示找到了e，将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)//如果size大于阈值，需要进行扩容。
resize();
afterNodeInsertion(evict);
return null;
}
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//老table
int oldCap = (oldTab == null) ? 0 : oldTab.length;//老的容量
int oldThr = threshold;//老的阈值
int newCap, newThr = 0;//新的长度和新的阈值
if (oldCap > 0) {//如果老表的长度大于0
if (oldCap >= MAXIMUM_CAPACITY) {//如果老的容量大于设定的最大容量
threshold = Integer.MAX_VALUE;//将阈值设为Integer的最大值，2的31次方-1；
return oldTab;//返回老表
}//新容量=老容量*2，如果新容量小于最大容量值并且老容量大于等于默认容量值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold，将阈值double之后直接设为新阈值
}//如果老阈值大于零，并且老的容量小于0，将初始容量设为阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;//构造函数使用设置初始容量相关的函数
else { // zero initial threshold signifies using defaults
//默认构造函数，第一执行put操作的时候。
newCap = DEFAULT_INITIAL_CAPACITY;//将容量设置为初始容量
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//新的阈值为默认的负载因子*容量
}
if (newThr == 0) {//如果新的阈值为0，重新设定新阈值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;//将阈值赋值
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建新的数组
table = newTab;//将table指向新创建的数组
if (oldTab != null) {//如果老数组不为空
for (int j = 0; j < oldCap; ++j) {//循环遍历数组
Node<K,V> e;//临时记录节点
if ((e = oldTab[j]) != null) {//记录数组中相应位置的节点，并判断是否为空，如果为空，直接跳过。不为空才进行处理
oldTab[j] = null;//将老数组中相应位置元素置空
if (e.next == null)//如果e没有下一个元素，表示这个数组内放置的只有一个元素
newTab[e.hash & (newCap - 1)] = e;//将元素移动到新数组对应位置即可
else if (e instanceof TreeNode)//如果节点是树，那么久使用红黑树的拆分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order，链表的拆分
Node<K,V> loHead = null, loTail = null;//低位区，头尾“指针”
Node<K,V> hiHead = null, hiTail = null;//高位区，头尾“指针”
Node<K,V> next;//下一个
do {
next = e.next;//将next后移，然后处理e
if ((e.hash & oldCap) == 0) {//如果计算结果值为0，表示处于低位
if (loTail == null)//没有尾指针
loHead = e;//将头部指针指向e
else//将尾部的下一个指向e
loTail.next = e;
loTail = e;//将尾部指针指向e
}
else {//如果计算结果不为0，表示处于高位
if (hiTail == null)//高位头指针为空
hiHead = e;//高位头指针指向e
else//高位头指针不为空
hiTail.next = e;//高位尾指针下一个指向e
hiTail = e;//高位尾指针移向e
}
} while ((e = next) != null);//将e重新指向空指针
if (loTail != null) {//低位尾指针不为空
loTail.next = null;//将尾指针下一位置空
newTab[j] = loHead;//将对应新数组位置设置为低位头指针
}
if (hiTail != null) {//如果高位尾指针不为空
hiTail.next = null;//将高位尾指针下一位置空
newTab[j + oldCap] = hiHead;//将新数组高位对应位置指向高位尾指针。
}
}
}
}
}//如果为空，直接返回新创建的数组
return newTab;
}
static final int hash(Object key) {
int h;
//如果key不为null，将key的hashCode亦或上key的HashCode
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
JDK1.8的相关代码
HashMap<Integer, Integer> hp = new HashMap<>();
hp.put(0, 0);
hp.put(16, 16);
hp.put(32, 32);//0，16，32，在没有扩容前，都放在0位置上
hp.put(1, 1);
hp.put(31, 16);
hp.put(2, 2);
hp.put(3, 3);
hp.put(4, 4);
hp.put(5, 5);
hp.put(6, 6);
hp.put(7, 7);
hp.put(8, 8);//此时size是12 ，容量是16，在插入9之后进行扩容
hp.put(9, 9);//在扩容后，16因为需要变化需要重新换位置，换到了高位上。
关于容量从16变化到32
判断是否需要重新换位置的标准是（hash&新容量-1）是否可以在原来的位置上。
但是上面的判断变化非常复杂，从而采用了一种简单的变化标准，就是下图中的变化。
其实判断的核心标准在于新增的高位变化了1，就是从原来的判断4位到判断5位。就是最高位的判断。其中判断新变化的第5位是否是1即可，因为是1表示需要移动位置。因为容量变为32之后，位置考虑的也只是hash值后5位。所以hash&oldCap!=0就是表示需要换位的相关元素，将它们拼成新的链表
关于新位置为什么使用[j + oldCap]，是因为只变化了最高位，这个最高位为1低位全为0在二进制上表示就oldCap
哈希表中链表扩容相关位运算
Android
使用了一个固定的节点对象，来存储null键的情况。
没有特别复杂的算法，一切都是看起来那么简单。。。
@Override public V put(K key, V value) {
if (key == null) {//插入空键
return putValueForNullKey(value);
}
//计算Hash值，这个hash值的计算需要
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);//计算表中的位置
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {//判断这位置是否有数据，如果没有向后移动
if (e.hash == hash && key.equals(e.key)) {//找到hash值相等和key相等的数据
preModify(e);//预修改数据
V oldValue = e.value;//找到了，修改数据
e.value = value;
return oldValue;
}
}
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {//如果size增加后，大于了阈值
tab = doubleCapacity();//容量扩容
index = hash & (tab.length - 1);//修改位置
}
addNewEntry(key, value, hash, index);//新增加键值对
return null;
}
private V putValueForNullKey(V value) {
HashMapEntry<K, V> entry = entryForNullKey;//空键节点
if (entry == null) {//如果不存在空键节点，创建一个
addNewEntryForNullKey(value);
size++;
modCount++;
return null;
} else {//如果存在空键节点，修改空键节点
preModify(entry);//预修改，主要针对LinkeHash修改的方法，在HashMap中是空方法。
V oldValue = entry.value;//修改值
entry.value = value;
return oldValue;
}
}
void addNewEntryForNullKey(V value) {
//创建一个空键的HashMapEntry
entryForNullKey = new HashMapEntry<K, V>(null, value, 0, null);
}
void preModify(HashMapEntry<K, V> e) { }
//在相应的位置创建一个新的条目即可
void addNewEntry(K key, V value, int hash, int index) {
table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}
//扩容，双倍扩容
private HashMapEntry<K, V>[] doubleCapacity() {
HashMapEntry<K, V>[] oldTable = table;//老表
int oldCapacity = oldTable.length;//老容量
if (oldCapacity == MAXIMUM_CAPACITY) {//如果老的容量已经等于最大值就返回老表
return oldTable;
}
int newCapacity = oldCapacity * 2;//新容量=老容量扩大2倍，因为初始容量都是2的倍数，最大容量也是2的倍数，所以扩容后不会超过
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);//确保新表容量是2的倍数
if (size == 0) {//如果size=0，不需要处理表中的数据
return newTable;//直接将新表返回
}
for (int j = 0; j < oldCapacity; j++) {//遍历老表
/*
* Rehash the bucket using the minimum number of field writes.
* This is the most subtle and delicate code in the class.
*/
HashMapEntry<K, V> e = oldTable[j];//记录位置的数据
if (e == null) {//如果数据为空，继续
continue;
}
int highBit = e.hash & oldCapacity;//链表首位数据高位的bit，其他位全是0
HashMapEntry<K, V> broken = null;//相等于尾节点
newTable[j | highBit] = e;// j | highBit等于j+highBit，因为j和highBit的位值有差异
//循环链表
for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
int nextHighBit = n.hash & oldCapacity;//计算链表其他数据的bit
if (nextHighBit != highBit) {//如果不相等，表示需要移动位置
if (broken == null)//如果broken为空，表示没有移动过
newTable[j | nextHighBit] = n;//直接移动数据即可
else//移动过数据，就将broken的后位置为n即可
broken.next = n;
broken = e;//将broken指向e，具体参考下图的演示
highBit = nextHighBit;//将高位置移动
}
}
if (broken != null)//如果broken不为空，将broken的后续节点指向空
broken.next = null;
}
return newTable;
}
Collections.java
public static int secondaryHash(Object key) {
return secondaryHash(key.hashCode());
}
private static int secondaryHash(int h) {
// Spread bits to regularize both segment and index locations,
// using variant of single-word Wang/Jenkins hash.
h += (h << 15) ^ 0xffffcd7d;
//-12931
//1111 1111 1111 1111 1100 1101 0111 1101
h ^= (h >>> 10);
h += (h << 3);
h ^= (h >>> 6);
h += (h << 2) + (h << 14);
return h ^ (h >>> 16);
}
Android中扩容时链表处理
3.2 增加Map中的元素
Java
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {//map中的数据大于0个
if (table == null) { // pre-size，主要针对空数组预加载阈值
float ft = ((float)s / loadFactor) + 1.0F;//这个值是map种的容量
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);//设定容量
if (t > threshold)//如果map中容量超过阈值，修改阈值
threshold = tableSizeFor(t);
}
else if (s > threshold)//如果容量查过阈值，那么修改扩容
resize();
//遍历，并将map中数据插入到HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
Android
循环一个个增加元素
@Override public void putAll(Map<? extends K, ? extends V> map) {
ensureCapacity(map.size());//确保容量足够
super.putAll(map);//调用父类的putAll方法
}
private void ensureCapacity(int numMappings) {
int newCapacity = Collections.roundUpToPowerOfTwo(capacityForInitSize(numMappings));//将容量扩容
HashMapEntry<K, V>[] oldTable = table;
int oldCapacity = oldTable.length;
if (newCapacity <= oldCapacity) {//确保需要的容量小于已有容量，直接返回
return;
}
if (newCapacity == oldCapacity * 2) {//如果新容量是老容量的2倍
doubleCapacity();//直接扩容，然后返回
return;
}
// We're growing by at least 4x, rehash in the obvious way
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
//新创建数组
if (size != 0) {
int newMask = newCapacity - 1;//新容量-1
for (int i = 0; i < oldCapacity; i++) {
for (HashMapEntry<K, V> e = oldTable[i]; e != null;) {
HashMapEntry<K, V> oldNext = e.next;//记录e的后节点
int newIndex = e.hash & newMask;//计算新位置
HashMapEntry<K, V> newNext = newTable[newIndex];//记录新位置的数据
newTable[newIndex] = e;//将新位置的数据设为e
e.next = newNext;//将e后继指向原来新位置的数据
e = oldNext;//将e指向原来e的后继，循环链表
}
}
}
}
AbstractMap.java
public void putAll(Map<? extends K, ? extends V> map) {
for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
put(entry.getKey(), entry.getValue());
}
}
四、删除元素
4.1删除Key相等的元素
在key相等的情况下就删除元素，默认的删除元素的方法
还有一个删除key相等和Value相等的元素方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
//哈希值、键、值、是否需要值相等、移动的（用于红黑树）？
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
//表，相应位置p节点，表长度，位置
Node<K,V>[] tab; Node<K,V> p; int n, index;
//表不为空，表长度大于0，表相应位置元素不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//需要删除的节点
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;//hash值相等和key相等，表示找到了元素
else if ((e = p.next) != null) {//没有直接找到元素，处理链表或红黑树
if (p instanceof TreeNode)//处理红黑树，找到节点
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {//处理链表
do {//找到hash和key相等的记录为node
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;//删除位置前的元素
} while ((e = e.next) != null);
}
}
//判断是否可以删除
// 节点不为空，是否需要值相等
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)//删除树的节点
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)//如果删除的是链表的头节点
tab[index] = node.next;//将数组指向链表的下一位置即可
else//将前节点的后继指向删除节点的后继
p.next = node.next;
++modCount;//修改次数增加
--size;//size减小
afterNodeRemoval(node);//LinkeHashMap使用
return node;
}
}
return null;
}
Android
@Override public V remove(Object key) {
if (key == null) {//如果key等于null，调用null的删除方法
return removeNullKey();//移除空元素
}
int hash = Collections.secondaryHash(key);//计算Hash值
HashMapEntry<K, V>[] tab = table;//表
int index = hash & (tab.length - 1);//计算位置
//循环链表，记录节点的前节点
for (HashMapEntry<K, V> e = tab[index], prev = null;
e != null; prev = e, e = e.next) {
//hash值相等和key相等，表示找到了元素，
if (e.hash == hash && key.equals(e.key)) {
if (prev == null) {//如果没有前节点，表示需要删除的链表的尾节点
tab[index] = e.next;
} else {//如果有将前节点的后节点指向新的后节点
prev.next = e.next;
}
modCount++;//修改次数增加
size--;//size-1
postRemove(e);//预删除
return e.value;
}
}
return null;
}
private V removeNullKey() {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null) {//如果e为null，表示没有存储空键值的元素
return null;
}
entryForNullKey = null;//将空元素置为空
modCount++;//修改次数
size--;//size减小
postRemove(e);//预删除，子类可以能有相应取消连接的实现
return e.value;
}
void postRemove(HashMapEntry<K, V> e) { }
五、修改元素
Java
除put外还有replace相关方法，
@Override
public V replace(K key, V value) {
Node<K,V> e;
//找到节点病替换节点的值
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
@Override
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
//找到key和value都相等的节点，替换这个节点的值
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
@Override
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Node<K,V>[] tab;
if (function == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
//循环遍历数组，处理数组中的数据
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
e.value = function.apply(e.key, e.value);
}
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
Android
没有replace相关的API
六、查询元素
Java
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
@Override
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;//如果查找的结果为空，就返回给定的默认值
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//找到hash对相应位置的元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//检查第一个节点key是否相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {//是否有后继节点
if (first instanceof TreeNode)//如果是树形结构，调用树形结构的获取方法
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {//循环遍历链表，直到找到相应的节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
Android
除了红黑树外与Java没有特殊差异
public V get(Object key) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
return e == null ? null : e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
}
七、其他
7.1 包含元素
Java
//包含Key
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
//是否包含值
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
//循环遍历数组、链表以及红黑树
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
Android
@Override
public boolean containsKey(Object key) {
if (key == null) {
return entryForNullKey != null;
}
//计算hash值
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
//遍历tab对应的链表
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return true;
}
}
return false;
}
@Override
public boolean containsValue(Object value) {
HashMapEntry[] tab = table;
int len = tab.length;
if (value == null) {//如果值为空，先遍历数组中是否有null值，如果有返回true，如果没有查询空键值对中是否包含值
for (int i = 0; i < len; i++) {
for (HashMapEntry e = tab[i]; e != null; e = e.next) {
if (e.value == null) {
return true;
}
}
}
return entryForNullKey != null && entryForNullKey.value == null;
}
// value is non-null，循环遍历判断是否包含相应的元素
for (int i = 0; i < len; i++) {
for (HashMapEntry e = tab[i]; e != null; e = e.next) {
if (value.equals(e.value)) {
return true;
}
}
}
//最后判断空键值对的值是否是需要查找的值
return entryForNullKey != null && value.equals(entryForNullKey.value);
}
7.2 集合的Size
Java
public int size() {
return size;
}
Android
@Override public int size() {
return size;
}
7.3 集合是否为空
Java
public boolean isEmpty() {
return size == 0;
}
Android
@Override public boolean isEmpty() {
return size == 0;
}
7.4 清空
Java
循环变量数组将数组元素置为空，红黑树和链表等待JVM自动回收
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
Android
使用了工具类，将数组及相应链表内的数据全部填充为空
@Override
public void clear() {
if (size != 0) {
Arrays.fill(table, null);
entryForNullKey = null;
modCount++;
size = 0;
}
}
八、遍历
8.1 键值对迭代器
Java
对应EntrySet的迭代器
//键值对Set
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
//键值对Set继承了抽象的Set
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }//返回HashMap的大小
public final void clear() { HashMap.this.clear(); }//清空数据
public final Iterator<Map.Entry<K,V>> iterator() {//迭代器
return new EntryIterator();
}
public final boolean contains(Object o) {//是否包含对象
if (!(o instanceof Map.Entry))//判断是否是键值对类型
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;//转换为对应的键值对
Object key = e.getKey();//获取Key
Node<K,V> candidate = getNode(hash(key), key);//获取节点的键值对
return candidate != null && candidate.equals(e);//判断节点是否相等
}
public final boolean remove(Object o) {//移除键值对
if (o instanceof Map.Entry) {//如果是Map的键值对
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
//找到键和值相等的键值对，并移除它
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
//拆分哈希表
public final Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
//Entry的键值对，继承了默认键值对
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
abstract class HashIterator {
Node<K,V> next; // next entry to return，下一个节点
Node<K,V> current; // current entry，当前节点，返回的节点
int expectedModCount; // for fast-fail，期望修改次数
int index; // current slot，当前的槽
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {//是否有下一个
return next != null;//下一个不为空
}
final Node<K,V> nextNode() {//下一个节点
Node<K,V>[] t;//
Node<K,V> e = next;//下一个节点
if (modCount != expectedModCount)//判断修改次数是否变化过
throw new ConcurrentModificationException();
if (e == null)//节点不为空，表示还有后续节点
throw new NoSuchElementException();
//如果next是null，就将next赋值为表中下一个不为null的值
//如果next不是null，那么next就是链表或者红黑树中的下一个值
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
//移除元素
public final void remove() {
Node<K,V> p = current;//当前节点
if (p == null)//如果当前节点为空，抛出异常
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;//将当前节点置为null，避免连续两次调用移除，并且不移动
K key = p.key;//key值相等
//移除node节点
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
Android
public Set<Entry<K, V>> entrySet() {
Set<Entry<K, V>> es = entrySet;
return (es != null) ? es : (entrySet = new EntrySet());
}
private final class EntrySet extends AbstractSet<Entry<K, V>> {
public Iterator<Entry<K, V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Entry))
return false;
Entry<?, ?> e = (Entry<?, ?>) o;
return containsMapping(e.getKey(), e.getValue());
}
public boolean remove(Object o) {
if (!(o instanceof Entry))
return false;
Entry<?, ?> e = (Entry<?, ?>)o;
return removeMapping(e.getKey(), e.getValue());
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
HashMap.this.clear();
}
}
Iterator<Entry<K, V>> newEntryIterator() { return new EntryIterator(); }
private final class EntryIterator extends HashIterator
implements Iterator<Entry<K, V>> {
public Entry<K, V> next() { return nextEntry(); }
}
private abstract class HashIterator {
int nextIndex;
HashMapEntry<K, V> nextEntry = entryForNullKey;
HashMapEntry<K, V> lastEntryReturned;
int expectedModCount = modCount;
HashIterator() {
if (nextEntry == null) {
HashMapEntry<K, V>[] tab = table;
HashMapEntry<K, V> next = null;
while (next == null && nextIndex < tab.length) {
next = tab[nextIndex++];
}
nextEntry = next;
}
}
public boolean hasNext() {
return nextEntry != null;
}
HashMapEntry<K, V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == null)
throw new NoSuchElementException();
HashMapEntry<K, V> entryToReturn = nextEntry;
HashMapEntry<K, V>[] tab = table;
HashMapEntry<K, V> next = entryToReturn.next;
while (next == null && nextIndex < tab.length) {
next = tab[nextIndex++];
}
nextEntry = next;
return lastEntryReturned = entryToReturn;
}
public void remove() {
if (lastEntryReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
HashMap.this.remove(lastEntryReturned.key);
lastEntryReturned = null;
expectedModCount = modCount;
}
}
8.2 Key迭代器
Java
public Set<K> keySet() {
Set<K> ks;
return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
}
//与EntrySet相同，只不过处理的Entry
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<K> iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
Android
@Override
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null) ? ks : (keySet = new KeySet());
}
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
int oldSize = size;
HashMap.this.remove(o);
return size != oldSize;
}
public void clear() {
HashMap.this.clear();
}
}
Iterator<K> newKeyIterator() { return new KeyIterator(); }
private final class KeyIterator extends HashIterator
implements Iterator<K> {
public K next() { return nextEntry().key; }
}
8.3 值迭代器
Java
public Collection<V> values() {
Collection<V> vs;
return (vs = values) == null ? (values = new Values()) : vs;
}
final class Values extends AbstractCollection<V> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<V> iterator() { return new ValueIterator(); }
public final boolean contains(Object o) { return containsValue(o); }
public final Spliterator<V> spliterator() {
return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
Android
@Override public Collection<V> values() {
Collection<V> vs = values;
return (vs != null) ? vs : (values = new Values());
}
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
Iterator<V> newValueIterator() { return new ValueIterator(); }
private final class ValueIterator extends HashIterator
implements Iterator<V> {
public V next() { return nextEntry().value; }
}
8.4 小结
- 三个迭代器都是一个迭代器的子类
- 如果遍历Map的话，建议使用EntrySet，这个效率稍高，不用再次调用get方法获取Value值
- Java和Android大同小异，除了Java多了一种数据结构红黑树
九、总结
- 关于底层数据结构：哈希桶（每个桶里放置链表或红黑树）
- 关于容量和负载因子：容量是哈希表的最大容量，负载因子是哈希Map的存储比例
阈值是最大容量*负载因子。而判断是否超过阈是采用size进行判断，并不是hashTable中数组的占有比例 - 影响哈希Map的效率最主要的方法是key对应类实现的hashCode。
- 可以设置key值为null和value值为null
- 与HashTable的区别
4.1. HashMap是线程非安全的，HashTable是线程安全的，Hashtable不允许key和value值为null，
4.2. 关于Hash值，HashMap中使用了一个函数来处理key.hashCode()方法，Hashtable直接使用了key.hashCode()方法作为hash值，这样也是为什么key值不能为null，表的位置信息是采用模运算，因为表的长度不是2的n次方。
4.3. Hashtable扩容是2倍+1，表的长度最小可以设为1。如果使用默认构造函数，那么长度是11，可以理解为默认长度是11.
参考
其他文章
容器解析
ArrayList解析
LinkedList解析
TreeMap解析(上)
TreeMap解析(下)
HashMap解析
LinkedHasMap解析(下)
Set解析
