在JDK1.6,JDK1.7中,HashMap采用位桶+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。而JDK1.8中,HashMap采用位桶+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。 简单说下HashMap的实现原理: 首先有一个每个元素都是链表(可能表述不准确)的数组,当添加一个元素(key-value)时,就首先计算元素key的hash值,以此确定插入数组中的位置,但是可能存在同一hash值的元素已经被放在数组同一位置了,这时就添加到同一hash值的元素的后面,他们在数组的同一位置,但是形成了链表,同一各链表上的Hash值是相同的,所以说数组存放的是链表。而当链表长度太长时,链表就转换为红黑树,这样大大提高了查找的效率。 当链表数组的容量超过初始容量的0.75时,再散列将链表数组扩大2倍,把原链表数组的搬移到新的数组中 即HashMap的原理图是:
一,JDK1.8中的涉及到的数据结构 1,位桶数组 transient Node[] table;//存储(位桶)的数组 2,数组元素Node实现了Entry接口 //Node是单向链表,它实现了Map.Entry接口 [Java] 纯文本查看 复制代码 static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
//构造函数Hash值 键 值 下一个节点
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
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;
}
//判断两个node是否相等,若key和value都相等,返回true。可以与自身比较为true
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry e = (Map.Entry)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
3,红黑树 [Java] 纯文本查看 复制代码 //红黑树
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent; // 父节点
TreeNode left; //左子树
TreeNode right;//右子树
TreeNode prev; // needed to unlink next upon deletion
boolean red; //颜色属性
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
//返回当前节点的根节点
final TreeNode root() {
for (TreeNode r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
|