Java HashMap概要记录
概述
简单介绍一下 Java 集合中的HashMap
Map
源码(1.8)中的定义:
特点: 没有重复的key对于map的这个方法大家肯定熟悉:Set keySet(); 所以key使用set存储 值 唯一,无序,允许为null
用于存储k-v结构的数据接口,其最主要的实现类:HashMap(实际工作中使用较多的) TreeMap
map集合框架图:
HashMap (重写了map的所有方法)
类定义:
对于map 而言hashmap在实际的运用中是使用最多的,首先为什么在实际运用中hashmap 使用最多呢 ?
Hash(哈希): hash算法绝对是该map 使用最多的功臣,对于开发而言很多内容我们需要快熟高效的性能,所以hash算法其实就是将一些很复杂或者数据量大的数据进行hash计算,将源数据和自己hash之后的标识进行匹配然后将计算出来的标志值用来进行索引放在字的key值链表数组里面;
hash方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
复制代码
业内大佬把这个函数叫做 '扰动函数' 具体解释的话,本身能力有限,大致一句话就是:使用或者函数减少map index 冲突。
hash方法先对当前key进行获取hashcode 然后于自身code值右移16位(Java 1.8之前是进行4次右移)的数值进行异或将index进行减少数值,后面在根据这个数字进行后续的判断处理。
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;
}
复制代码
上面是整个map put 数据的一些判断: 其中 putTreeVal 这个也是1.8之后对于map存储数据结构的优化处理-->树化。 在1.7之前的map的entry(key-value)的数据其实就是一定hash之后数组形式存储在数据库,eg:
上面的是正常 情况下,一旦出现数据碰撞的化就会进行每一个index 衍生为一个链表
以上两个属于1.8之前的存储规则:
对于map来说为什么数据存储之后是无序的呢? map每一次进行数据存储的时候回将当前的数据进行hash然后进行后续判断,其中有一个就是判断当前数据的容量是否达到了扩容的标准,一旦达到扩容的标准的化就会进行数据重新hash所以位置是不定的,并且一旦存在数据碰撞(index冲突),会将新数据放在链表的头部(源码作者觉得最新插入的数据,访问的概率更大);
然后对于map 还有一个比较深的内容是扩容机制: 1.8之后不单单进行了简单的扩容,并且还引用了Tree的概念,一旦容量达到 TREEIFY_THRESHOLD 默认值 8 就会将index链表进行红黑树扩容 上面的源码中的 putTreeVal 树化!!!
其他方法
面试题
map 扩容机制 (由于该篇篇幅太长,扩容后续会详细出一篇吧)
map 循环的几种常见方式
//方法1 entrySet + iterator
Set<Map.Entry<Object, Object>> entries = map.entrySet();
Iterator<Map.Entry<Object, Object>> iterator = entries.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next().getKey()+":"+iterator.next().getValue());
}
复制代码
//方法2 entrySet + for
for (Map.Entry<Object, Object> entry : entries) {
System.out.println(entry.getKey()+":"+entry.getValue());
}
复制代码
//方法3 keySet +for
Set<Object> objects = map.keySet();
for (Object object : objects) {
System.out.println(object+":"+map.get(object));
}
复制代码
//方法4 不需要对应的 只展示值
Collection<Object> values = map.values();
for (Object value : values) {
}
Set<Object> objects1 = map.keySet();
for (Object o : objects1) {
}
复制代码
//方法5 1.8 lambda
map.forEach((k,v)->System.out.println("key: " + k + " value:" + v));
复制代码