HashMap的底层数据
HashMap底层采用数组加链表的数据结构存储键值对
HashMap根据key的哈希值转换为数组的下标将键值对存入数组中，数组的元素是一个链表，冲突的key放置在数组的同一个位置，使用链表将冲突的数据链接起来
底层结构如下：
/**
* An empty table instance to share when the table is not inflated.
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
可见数组存储的元素是Entry,而Entry表示链表的节点存储了key,value,key的hash值，指向下一个节点的指针域next，Entry数据hashCode()方法是通过key的hash值和value的hash值异或得到的。equals方法判断两个entry相等的标准是key相等且value相等。重写equals方法必须重写hashCode方法，满足两个对象相等，则这两个对象的hash值必须相等。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
根据hash值计算桶中的位置
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);
}
数组的长度是2的整数幂，h$(length-1)等价于
h % length
通过位运算来实现取余运算，比较节省cpu运行时间
根据key获取Entry
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
首先判断size是否为0，size为0表示HashMap中没有键值对，此时通过key获取value必然返回null,然后判断key是否为null,null作为key，其hash值为0，null key在entry数组中的位置为index=0处
key不为null的话通过indexFor(hash, table.length)计算桶的位置 。
根据桶的位置获取链表头，然后遍历链表获取所求的entry
Entry<K,V> e = table[indexFor(hash, table.length)];
此时的e表示链表的头部，此链表的所有节点的key的hash值相同，但是key不同，因此扫描链表，获取对应的key的entry，然后返回这个ertry.
键key为null时候的特殊处理
HashMap允许null的键和null的值，键为null的entry都是放在entry数组索引为0地方
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
如果size==0，则value必然为null，直接返回null
否则通过Entry<K,V> e = table[0]获取链表头部
通过e.key == null找到key为null的entry，返回此entry的value
HashMap允许null的键和null的值，键为null的entry都放在entry数组索引为0地方，即下标为0的桶内（也有可能其他非null键hash值刚好为0，因此需要扫描比较）
通过键获取值
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
分类处理，key为null通过getForNullKey()获取对应的value
否则通过getEntry(key)获取对应的entry，通过entry获取value
向entry链表中添加一个新的entry
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
首先判断size >= threshold，如果存储的键值对数量size大于阈值threshold的话，需要扩容，然后rehash，重新计算hash值和桶的位置
然后调用createEntry把entry添加到链表头
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
根据key删除数据
根据key的hash值找到桶，遍历桶中的链表，找到对应的key的entry,删除。删除的办法就是entry的前序节点的后继指针直接指向entry节点的后继节点
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
如果size==0，HashMap中没有保存任何键值对，对任何key取value均返回null
否则:
计算key的hash值，key==null设置key的hash值为0
否则通过hash(key)计算hash值
然后根据key的hash值计算桶的位置
判断是否包含某个value
这篇文章介绍的十分详细：http://www.importnew.com/28263.html
网友评论