Java中HashMap相关知识点
HashMap使用
哈希表
哈希表也称散列表,根据关键码值key 进行访问的数据结构,也就是说,能够将关键码映射到表中一个位置我们就可以去访问其记录value,加快查找的速度,这个映射函数叫做散列函数,存放记录的数组叫做散列表。
数组:寻址容易O(1),插入和删除困难O(N)
链表:寻址困难O(N),插入和删除容易O(1)
综合两者的特性,变成了一个寻址容易,插入删除也容易的数据结构哈希表有多种不同的结构(实现),我们介绍的是最常用的结构-拉链法(链地址法)
Map接口
Map,图,是一种存储键值对映射的容器,在Map中键可以是任意类型的对象,但是键不允许重复的,每一个键对应有一个值。
public class Hash {
public static void main(String[] args) {
//声明hashmap对象
HashMap<String, Integer> map = new HashMap<>();
//添加数据put
map.put("a",1);
map.put("b",2);
map.put("c",3);
map.put("d",4);
map.put("e",5);
//根据键获取值 key
System.out.println(map.get("c"));
//获取map中键值对的个数
System.out.println(map.size());
//判断map集合是否包含为key的键值对
System.out.println(map.containsKey("d"));
//判断map集合是否包含值为value的键值对
System.out.println(map.containsValue(3));
//根据键删除map中的键值对
System.out.println(map.remove("e"));
//获取hashmap中的所有键值对
Iterator<Map.Entry<String,Integer>> iterator = map.entrySet().iterator();
while(iterator.hasNext()){
Map.Entry<String, Integer> next = iterator.next();
System.out.println(next.getKey()+":: "+next.getValue());
}
}
}
HashMap底层结构
HashMap基于哈希表的Map接口的非同步实现,继承自AbstractMap,AbstractMap是部分实现Map接口的抽象类。
jdk1.8之前:数组+链表
jdk1.8:数组+链表+红黑树
红黑树:
红黑树是一种自平衡二叉查找树 它在O(log2 N)的时间内做查找、添加、删除红黑树和AVL树是二叉查找树的变体,红黑树的性能要好于AVL树
红黑树特点:
1)每个节点是红色或黑色
2)根节点一定是黑色
3)每个叶子节点是黑色
4)如果一个节点是红色,则叶子节点必须是黑色
5)每个节点到叶子节点所经过的黑节点的个数必须是一样的。
当JVM存储HashMap的K-V时,仅仅通过Key来决定每一个Entry的存储槽位(Node[]中的index)。并且Value以链表的形式挂载到对应槽位上即可(1.8之后如果长度大于8则转为红黑树)。
HashMap之所以称之为HashMap是因为HashMap在put(String,Object)的时候JVM会对存入的对象进行一次hash(所有对象都是继承Object,而hashcode方法来自Object类中),从而获取到这个对象的hash值,接着JVM就根据这个hash值来决定该元素的存储位置。
如果发生两个Key存储到了同一个位置,则发生了Hash冲突(碰撞),Java采用的数组 + 链表方式就发挥作用了。Java采用链地址法(哈希值相同的元素构成一个链表,链表头指针指向Node[]的index),避免了Hash冲突的问题。Hash冲突发生后,这个槽位中存储的不是一个Entry而是多个Entry,此时就使用到了Entry链表。JVM是按照顺序去遍历每一个Entry,一直到查找到对应的Entry为止(链表查询)。如果hashcode相同,发生了hash冲突,新存入的值会覆盖旧的值,并且将旧的值返回。
HashMap扩容机制
HashMap中有resize(),当HashMap的元素个数超过数组的容量(length),进行扩容,默认情况下数组容量是16,当HashMap中的元素个数超过12个时,超过了临界值(就是源码中的threshold),需要把数组大小扩容一倍,然后通过rehash(重哈希),重新计算每个元素在数组中的位置。
HashMap源码分析
1)类的继承关系
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
1、HashMap允许空值和空键
2、HashMap是非线程安全
3、HashMap元素是无序 LinkedHashMap TreeMap(HashTable不允许为空 线程安全)
2)类的属性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //16 默认初始容量 用来给table初始化
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f; //扩容机制
static final int TREEIFY_THRESHOLD = 8; //链表转为红黑树的节点个数
static final int UNTREEIFY_THRESHOLD = 6;//红黑树转为链表的节点个数
static final int MIN_TREEIFY_CAPACITY = 64;
static class Node<K,V> implements Map.Entry<K,V>
transient Node<K,V>[] table; //哈希表中的桶
transient Set<Map.Entry<K,V>> entrySet; //迭代器遍历的时候
transient int size;
int threshold;
final float loadFactor;
3)类中重要的方法(构造函数 put remove resize)
构造函数中并未给桶进行初始化
put方法
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//resize() 初始化(和扩容)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//当前位置不存在节点,创建一个新节点直接放到该位置
else{
//当前位置存在节点 判断key是否重复
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断第一个节点的key是否与所要插入的key相等
//hashCode 表示将对象的地址转为一个32位的整型返回 不同对象的hashCode有可能相等
//比较hash相比于使用equals更加高效
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;
//判断e是否是key重复的节点
p = e;
}
}
}
Hash算法
resize时机
1)table==null
2)table需要扩容的时候
过程
1)table进行扩容
2)table原先节点进行重哈希
a.HashMap的扩容指的是数组的扩容,因为数组的空间是连续的,所以需要数组的扩容即开辟一个更大空间的数组,将老数组上的元素全部转移到新数组上来
b.在HashMap中扩容,先新建一个2倍原数组大小的新数组,然后遍历原数组的每一个位置,如果这个位置存在节点,则将该位置的链表转移到新数组
c.在jdk1.8中,因为涉及到红黑树,jdk1.8实际上还会用到一个双向链表去维护一个红黑树中的元素,所以jdk1.8在转移某个位置的元素时,首先会判断该节点是否是一个红黑树解节点,然后遍历该红黑树所对应的双向链表,将链表中的节点放到新数组的位置当中
d.最后元素转移完之后,会将新数组的对象赋值给HashMap中table属性,老数组将会被回收。
HashMap常见面试题
1)JDK1.7与JDK1.8HashMap有什么区别和联系
2)用过HashMap没?说说HashMap的结构(底层数据结构 + put方法描述)
3)说说HashMap的扩容过程
4)HashMap中可以使用自定义类型作为其key和value吗?
5)HashMap中table.length为什么需要是2的幂次方
6)HashMap与HashTable的区别和联系
7)HashMap、LinkedHashMap、TreeMap之间的区别和联系?
8)HashMap与WeakHashMap的区别和联系
9)WeakHashMap中涉及到的强弱软虚四种引用
10)HashMap是线程安全的吗?引入HashTable和ConcurrentHashMap
上一篇: JDK1.8新特征之Optional
下一篇: JDK1.8源码之LinkedList