1.数据结构
数组+链表的形式 【】【】【】【】【】
| | | | |
【】【】【】【】【】
数组长度:固定,即初始化HashMap时的capacity。当需要数组长度时,会rehash,重新计算容器中所有值的位置
链表长度:可以扩展,即冲突的对象放入链表中
2.如何从map中寻找值
public V get(Object key) {
Object k = maskNull(key);
int hash = hash(k);
int i = indexFor(hash, table.length);
Entry<K,V> e = table[i];
while (true) {
if (e == null)
return null;
if (e.hash == hash && eq(k, e.key))
return e.value;
e = e.next;
}
}
static int hash(Object x) {
int h = x.hashCode();
h += ~(h << 9);
h ^= (h >>> 14);
h += (h << 4);
h ^= (h >>> 10);
return h;
}
static int indexFor(int h, int length) {
return h & (length-1);
}
a.计算hash值(计算hash值,采用这种旋转Hash函数的主要目的是让原有hashCode的高位信息也能被充分利用,且兼顾计算效率以及数据统计的特性)
b.通过hash值和capcity作位运算,获取数组中的index
c.在指定数组元素中,用equals索引链表,获得查询的值
3.几个变量
initialCapacity:初始化map中元素的个数的参数,不代表是最好map中最后设置的值
loadFactor:负载因子
capacity:Find a power of 2 >= initialCapacity,实际容量
threshold:capacity*loadFactor=threshold,当map中元素的数据>threshold时,capacity会double,然后会做最耗性能的resize
4.initialCapacity的参数值,一定要根据业务估算,否则可能会rehash,浪费性能
5.为何将capacity设为2的N次方?
因为java可以利用位运算作取模运算,提供运行速度
6.非线程安全的Map VS Collections.synchronizedMap
fail-fast机制(比如,循环遍历时,不能添加或者删除map中元素)
7.linkedHashMap VS LRU(最近最久未使用算法)
a.实现方式:HashMap的子类,利用双链表维持内部元素的关系
b.内部header、before、after3个指针引用
c.由于增加了维护链接列表的开支,其性能要比 HashMap 稍逊一筹,不过有一点例外:LinkedHashMap的迭代所需时间与其的所包含的元素成比例;而HashMap 迭代时间很可能开支较大,因为它所需要的时间与其容量(分配给Key空间的长度)成比例。一言以蔽之,随机存取用HashMap,顺序存取或是遍历用 LinkedHashMap。
d.缺省情况下,LinkedHashMap采取的更新策略是类似于队列的FIFO,如果你想实现更复杂的更新逻辑比如LRU(最近最少使用)等,将removeEldestEntry与accessOrder一起使用,就可以实现最基本的内存缓存。如果accessOrder被设置为true,则每次访问元素时,都将该元素移至head的前面,即链表的尾部。
8.WeakHashMap
a.强引用、软引用、弱引用、虚幻引用
b.WeakHashMap采用的策略是,只要作为key的对象已经不存在了(超出生命周期),就不会阻止垃圾收集器清空此条目,即使当前机器的内存并不紧张。
分享到:
相关推荐
马士兵老师HashMap学习笔记
通过hash函数计算的结果与capacity-1进行且运算,得到buckets的index,若buckets[index]为空,则直接赋值,若不为空,首先查看首
hashmap的底层及源码解析,很适合大家的学习,不要积分。
hashMap和hashTable的区别,大家可以下载学习学习。
这个文档“ HashMap详解(通俗易懂)”很好的阐述了hashmap的底层数据结构示意,希望对学习java的人有帮助
这是一套PPT,讲述的内容是Java的JDK中内置的几种常用的集合框架工具类的知识,重点讲解HashMap,因为不让上传视频,就先传个PPT试试;
黑马程序员HashMap的笔记,面试必问,笔记很好,内容言简意赅,看完收获很多,希望能帮助大家的学习
hashmap的C++实现,对于学习C++方面的很有用
深入解读大厂java面试必考点之HashMap全套学习资料
Java集合专题总结:HashMap 和 HashTable 源码学习和面试总结
主要hashMap源码,包括put,get等,其中将代码风格修改为更易懂的风格,注释也更简洁明了,可以帮助学习hashMap的同学更简单的学习hashMap
全手写HashMap精简版Demo ,可直接允许查看效果,适合新手入门学习源码
hashmap中hash函数的构造问题,提供了各种构造方法。以及比较函数的构造 挺适合入门学习的
NULL 博文链接:https://zhangshixi.iteye.com/blog/672697
对HashMap的put方法的源码进行详细解读,分析put方法源码中的内在逻辑关系,欣赏源码独特之美,从中学习更为精致的编程思维
NULL 博文链接:https://128kj.iteye.com/blog/1749453
java代码-使用java解决手写hashMap的源代码 ——学习参考资料:仅用于个人学习使用!
哈希表HashMap解题套路【LeetCode刷题套路教程7】
一线大厂BATJ面试题讲解-hashmap原理实现
HashMap、ConcurrentHashMap源码级解读,并且对比了JDK7和8实现的不同,进行了大量的解释,结合了多个学习视频