面试中如何回答HashMap的工作原理

Question

如题所述

Answer 1

用过哪些Map类，都有什么区别，HashMap是线程安全的吗,并发下使用的Map是什么，他们
内部原理分别是什么，比如存储方式，hashcode，扩容，默认容量等。
JAVA8的ConcurrentHashMap为什么放弃了分段锁，有什么问题吗，如果你来设计，你如何
设计。
有没有有顺序的Map实现类，如果有，他们是怎么保证有序的。

hashmap的实现原理，https://blog.csdn.net/mbshqqb/article/details/79799009

下面是自己的总结:

存储结构:
里面存储的是一个entry数组，每个数组元素中的结构是一个entry链表
Entry是map中的一个静态内部类，其中的变量有:key,value,hashcocd,下一个Entry

什么是hash？
又称散列，将任意长度的输入通过散列算法转换成固定长度的输出，该输出就是散列值。这是一种压缩映射，散列值的空间通常远小于输出的空间。不同的输入有可能会散列出相同的输出，因此不能从散列值来确定唯一的输入值。这也是为什么比较两个对象不能仅仅使用hashcode方法比较的原因。

hash碰撞:
对不同的值进行hash运算生成了相同的散列值。这个是不可避免的，但是我们需要尽量的减少其带来的损失。
(1)设计好的hash算法让其尽可能的分布均匀
hashmap中的hash算法解析
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
让key的hashcode本身与它右移16位异或，是为了让它的高位与低位混合，增加低位的随机性，同时也变相保持了高位的特征

计算元素位置的算法:
int index = hash & (arrays.length-1);
那么这也就明白了为什么HashMap的数组长度是2的整数幂。比如以初始长度为16为例，16-1 = 15，15的二进制数位00000000 00000000 00001111。可以看出一个基数二进制最后一位必然位1，当与一个hash值进行与运算时，最后一位可能是0也可能是1。但偶数与一个hash值进行与运算最后一位必然为0，造成有些位置永远映射不上值。

对于null值的处理
hashmap是接受null值的，null值被放在数组的第一个元素当中，取出来的时候怎么处理呢？

hashmap的工作原理？
它的里面有一个Entry数组，在put时我们先根据key值计算出hashcode，进而计算出该元素在数组中的位置，将健值对封装在Map.Entry对象中，然后存储在数组中

若产生hash冲突怎么办？
每个数组元素的位置都是一个链表结构，若计算出来的hashcode相同则将元素追加到该链表当中，这是hashmap的处理方式

在取元素的时候，先计算key值对应的hashcode ，找到元素所在的位置，然后调用key的equals方法去遍历链表，最后找到元素

还有哪些解决hash冲突的方法？
开放定址法
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
再哈希法
这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
链地址法
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
建立公共溢出区
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

默认的负载因子0.75
当map的大小超过当前容量的百分之75时会进行自动扩容，会将原来的对象重新放到新的数组中

rehash 的过程是什么样子的？
说白了就是先resize，生成一个新的Entry数组，再transfer将原数组中的值重新计算index放入新的数组中，然后改变阈值为新的长度x负载因子

如果key为null，这始终会被散列到table[0]的桶中，即使是rehash的过程也是一样。非null的key也有可能会被散列到table[0]的位置，例如上图中key=“f”，而且相同的key在在不同的时间可能会被散列到不同的位置，这与rehash有关。

这个过程中容易发生什么问题呢？
容易产生条件竞争，如果在扩容的过程中put数据，会造成意想不到的结果。或者如果两个线程都触发了扩容，也会存在问题

这块有没有遇到过什么比较好的例子？

jdk1.8以后改成了红黑树，为什么？说一下红黑树的原理？

hashmap与hashtable的区别？
HashTable和HashMap的实现原理几乎一样，差别无非是
HashTable不允许key和value为null
HashTable是线程安全的
但是HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁。
多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。

篇幅有限，未完待续

Answer 2

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap，都知道哪里要用HashMap，知道HashTable和HashMap之间的区别，那么为何这道面试题如此特殊呢？是因为这道题考察的深度很深。这题经常出现在高级或中高级面试中。投资银行更喜欢问这个问题，甚至会要求你实现HashMap来考察你的编程能力。ConcurrentHashMap和其它同步集合的引入让这道题变得更加复杂。让我们开始探索的旅程吧！

本回答被网友采纳