设计作品网站有哪些,租用域名与空间的网站并会使用,网站设计需求,宣传网页文章目录一、背景知识1、什么是Map#xff1f;2、什么是Hash#xff1f;3、什么是哈希表#xff1f;4、什么是HashMap?5、如何使用HashMap#xff1f;6、HashMap有哪些核心参数#xff1f;7、HashMap与HashTable的对比#xff1f;8、HashMap和HashSet的区别#xff1f;…
文章目录一、背景知识1、什么是Map2、什么是Hash3、什么是哈希表4、什么是HashMap?5、如何使用HashMap6、HashMap有哪些核心参数7、HashMap与HashTable的对比8、HashMap和HashSet的区别9、什么是LinkedHashMap和TreeMap二、HashMap的实现原理10、HashMap的数据结构11、HashMap put元素的原理12、HashMap get元素的原理三、红黑树13、为什么要将链表转化为红黑树14、链表元素超过8转化为红黑树那为什么不是红黑树元素小于等于8转化为链表而是小于等于615、链表元素超过8是否一定转化为红黑树三、hash计算和index计算16、HashMap如何计算K的hash值17、为什么不用K的hashCode值直接作为hash值而是将hashCode值进行无符号右移16位再异或的复杂操作18、HashMap如何计算K的数组下标四、HashMap的扩容19、HashMap什么时候扩容20、为什么HashMap的容量必须是2的幂21、JDK7如何实现HashMap的扩容22、1.7为什么采用头插法23、头插法为什么会造成HashMap的死循环24、JDK8做了哪些改进避免死循环25、JDK8扩容的优化点26、HashMap线程安全吗27、什么是ConcurrentHashMap28、ConcurrentHashMap JDK7的实现原理29、ConcurrentHashMap JDK8的实现原理30、JDK8对HashMap做了哪些优化一、背景知识 面试过程中面试官的死亡连你说你看过很多源码是吗那你说说hashmap的底层实现什么条件下会自动扩容的?为什么要有 红黑树?什么条件下会有?扩容因子为什么是0.75有研究过吗? 下来就来彻底了解一下HashMap吧 1、什么是Map Map是一种集合接口提供了一系列操作K-V的方法HashMap、HashTable都是Map接口的实现类。 2、什么是Hash Hash 音译为 “哈希” 也叫 “散列” 。 哈希的本质是通过哈希函数对原始数据进行有损压缩得到固定长度的输出即哈希值通过哈希值唯一标识原始数据。 若不同的原始数据被有损压缩后产生了相同的结果该现象称为哈希碰撞。 3、什么是哈希表 哈希表是一种数据结构它可以提供较高的存取效率。 【原理】 1、向哈希表插入元素时会先根据哈希函数计算K对应的存储位置再put元素 2、查询时根据哈希函数计算K对应的存储位置直接访存储位置获取元素查询效率高。 【基本概念】
4、什么是HashMap? HashMap继承了AbstractMap类是Map接口的一种实现用于存储K-V数据结构的元素底层通过哈希表实现了较快的存取效率。 5、如何使用HashMap
Map map new HashMap(); // 创建HashMap对象
map.put(数学, 91 ); // 存放元素
map.put(语文, 92 ); // 存放元素
map.put(物理, 94 ); // 存放元素
int score map.get(语文); // 获取元素值
for(Object key : map.keySet()) { // 遍历元素System.out.println(科目key 的成绩是 map.get(key));
}
map.remove(物理); // 删除元素6、HashMap有哪些核心参数
1、默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY 1 4; // 162、最大容量
static final int MAXIMUM_CAPACITY 1 30;3、默认负载因子
static final float DEFAULT_LOAD_FACTOR 0.75f;4、树形化阈值
static final int TREEIFY_THRESHOLD 8;5、解树形化阈值
static final int UNTREEIFY_THRESHOLD 6;7、HashMap与HashTable的对比
【相同点】 都用于存储K-V元素 【不同点】 HashMap可接受null键值和值Hashtable则不能HashMap线程不安全HashTable线程安全方法都加了synchronizedHashMap继承AbstractMap类HashTable继承Dictionary类HashMap的迭代器(Iterator)是fail-fast迭代器HashTable的enumerator迭代器不是fail-fast所以遍历时如果有线程改变了HashMap增加或者移除元素将会抛出 ConcurrentModificationException。HashMap默认容量16扩容为old2HashTable默认容量11扩容为old21。 8、HashMap和HashSet的区别 HashSet实现Set接口不允许集合中有重复值HashMap实现Map接口存储键值对K不允许重复。 9、什么是LinkedHashMap和TreeMap LinkedHashMap内部维护一个链表存储了K的插入顺序迭代时按照插入顺序迭代。 TreeMap底层是一颗红黑树containsKey、get、put、remove方法的时间复杂度都是 log(n)按K的自然顺序排列如整数的从小到大也可指定Comparator比较函数。 二、HashMap的实现原理
10、HashMap的数据结构 JDK1.7及之前HashMap的内部数据结构是数组链表。 JDK1.8开始当链表长度 8时会转化为红黑树当红黑树元素个数 ≤ 6时会转化为链表。 11、HashMap put元素的原理 12、HashMap get元素的原理 三、红黑树
13、为什么要将链表转化为红黑树 链表长度太长时红黑树的存取效率比链表高。 14、链表元素超过8转化为红黑树那为什么不是红黑树元素小于等于8转化为链表而是小于等于6 如果链表和红黑树互相转换的阈值固定是8当HashMap元素个数在8左右变更时 会导致树和链表数据结构的频繁变更降低性能所以中间预留buffer。 15、链表元素超过8是否一定转化为红黑树 链表长度大于8 数组长度大于64才会树形化否则只是resize扩容。 为什么呢因为数组小而链表长的场景将链表转换为树治标不治本应优先扩容数组。 三、hash计算和index计算
16、HashMap如何计算K的hash值 hash值 (key null) ? 0 : (h key.hashCode()) ^ (h 16); 17、为什么不用K的hashCode值直接作为hash值而是将hashCode值进行无符号右移16位再异或的复杂操作 Object的hashCode()函数返回的值是int型值范围从-2147483648到2147483648转化为2进制有32位如、1011000110101110011111010011011。 使用右移、异或的操作可以充分利用K的hashCode值高低位不同的特性以减少hash碰撞的可能提升查询效率。 18、HashMap如何计算K的数组下标 index h (length-1) 四、HashMap的扩容
19、HashMap什么时候扩容 当元素数量超过阈值时扩容阈值 数组容量 * 加载因子。数组容量默认16加载因子默认0.75所以默认阈值12。容量上限为1 30 20、为什么HashMap的容量必须是2的幂 index h (length-1)2的幂次方-1都是1可以充分利用高低位特点减少hash冲突。 21、JDK7如何实现HashMap的扩容
源码、
void resize(int newCapacity) {Entry[] oldTable table;int oldCapacity oldTable.length;if (oldCapacity MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return;}Entry[] newTable new Entry[newCapacity];transfer(newTable, initHashSeedAsNeeded(newCapacity));table newTable;threshold (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY 1);
}void transfer(Entry[] newTable, boolean rehash) {int newCapacity newTable.length;for (EntryK,V e : table) {while(null ! e) {EntryK,V next e.next;if (rehash) {e.hash null e.key ? 0 : hash(e.key);}int i indexFor(e.hash, newCapacity);e.next newTable[i];newTable[i] e;e next;}}
}不想看源码 直接看我整理的简单流程图 22、1.7为什么采用头插法 刚添加的元素被访的概率大。 23、头插法为什么会造成HashMap的死循环 【step1】现有HashMaptable大小为2里面有3个元素在index1处。 【step2】有2个线程同时触发了扩容但线程2刚启动扩容就被挂起此时线程2内e指向了key(A)其next指向了key(B)而线程1完成了扩容。 【step3】线程2被调度回来线程2内当前待调整元素e指向A所以头插A。此时e.nextB待调整B。 【step4】e next指向B所以头插B此时e.next table[i] 本来应该指向C但由于线程1已经完成了扩容所以又指向了A。 【step5】头插A形成环。 24、JDK8做了哪些改进避免死循环 1、链表太长转换为红黑树减少死循环发生的可能 2、1.8使用尾插法在扩容时会保持链表元素原来的顺序解决了死循环题但解决不了线程不安全题。 25、JDK8扩容的优化点 1、头插法改为尾插法解决链表死循环题。 2、扩容的效率更高 扩容前index hash(oldTable.length-1) 扩容后index hash(oldTable.length*2-1) 唯一的区别是 length -1多了一个高位1参与运算如果hash对应的位置是0则Node的index没变如果hash对应位置是1则newIndex oldIndex oldLength。 即得出结论、扩容后Node的位置要么不变要么移动odLength。 因此在扩容时不需要重新计算元素的hash了只需要通过 if ((e.hash oldCap) 0) 判断最高位是1还是0就可以确定index效率更高。 【线程安全】
26、HashMap线程安全吗 HashMap非线程安全线程安全的Map可以使用ConcurrentHashmap。 27、什么是ConcurrentHashMap HashMap线程不安全多线程环境可以使用Collections.synchronizedMap、HashTable实现线程安全但性能不佳。 ConurrentHashMap比较适合高并发场景使用。 28、ConcurrentHashMap JDK7的实现原理
1、数据结构、Segment数组HashEntry链表数组 ConcurrentHashMap由一个Segment数组构成默认长度16Segment继承自ReentrantLock所以加锁时Segment数组元素之间相互不影响所以可实现分段加锁性能高。 Segment本身是一个HashEntry链表数组所以每个Segment相当于是一个HashMap 。 2、put元素原理 3、get元素原理 get()操作不需要加锁是因为HashEntry的元素val和指针next都使用volatile修饰在多线程环境下线程A修改Node的val或新增节点时对线程B都是可见的。 29、ConcurrentHashMap JDK8的实现原理
1、数据结构、Node数组链表/红黑树类似1.8的HashMap。 摒弃Segment使用Node数组链表红黑树的数据结构。 桶中的结构可能是链表也可能是红黑树红黑树是为了提高查找效率。 并发控制使用Synchronized和CAS来操作整体看起来像是线程安全的JDK8 HashMap。 2、存放元素原理 3、获取元素原理 计算hash - 计算数组下标 - 遍历节点 30、JDK8对HashMap做了哪些优化 1、引入红黑树 提升元素获取速度。 2、头插法改为尾插法解决链表死循环题。 3、扩容的效率更高
