详见语雀https://www.yuque.com/xingsujtpw/gmrbgh/pv0u9pvyb36lcgs2?singleDoc#HashMap相关面试题4.3面试题-说一下HashMap的实现原理#我的表述 采用键值对, 键是Object对象, 而值又是数组索引下标映射对象 --上述是错误的 #自己重新表述一下 **HashMap的数据结构 底层使用hash表数据结构即数组 链表或 数组 红黑树当我们往HashMap中put元素时利用key的hashCode重新hash计算出当前对象的元素在数组中的下标存储时如果出现hash值相同的key此时有两种情况。a. 如果key相同则覆盖原始值b. 如果key不同出现冲突则将当前的key-value放入链表或红黑树中获取时直接找到hash值对应的下标在进一步判断key是否相同从而找到对应值。面试官追问HashMap的jdk1.7和jdk1.8有什么区别#我的表述 HashMap的jdk1.7只有链表, 而jdk1.8不仅有链表, 还有红黑树JDK1.8之前采用的是拉链法。拉链法将链表和数组相结合。也就是说创建一个链表数组数组中每一格就是一个链表。若遇到哈希冲突则将冲突的值加到链表中即可。jdk1.8在解决哈希冲突时有了较大的变化当链表长度大于阈值默认为8 时并且数组长度达到64时将链表转化为红黑树以减少搜索时间。扩容 resize( ) 时红黑树拆分成的树的结点数小于等于临界值6个则退化成链表4.4面试题-HashMap的put方法的具体流程#我的表述 第一, 实例化HashMap 第二, 使用key的hashCode重新hash计算当前对象的元素在数组中的下标 第三, 存储值时, 会出现hash相同的key两种情况, 若相同则覆盖原来的值, 若不同即hash冲突, 则将其存储到对应的链表中 #自己重新表述一下 **第一, 判断数组是否为空(懒加载)第二, 计算数组下标 : (n - 1) hash第三, 判断该槽位有没有数据第四, 槽位为空, 直接put进去第五, 槽位不为空, 判断key是否相同第六, 判断是不是红黑树节点第七, 是链表, 遍历链表, 尾部插入第八, 判断size是否超过阈值业务场景用HashMap缓存菜品列表避免重复查数据库需求运营后台频繁查看起售中的菜品列表每次都要查数据库很慢。用HashMap做缓存第一次查完存起来后面直接从缓存取。DishService中ServicepublicclassDishService{// 缓存key是状态1起售value是该状态下的菜品列表privateHashMapInteger,ListDishdishCachenewHashMap();publicListDishgetDishesByStatus(Integerstatus){// 1. 先从缓存取ListDishdishListdishCache.get(status);if(dishListnull){// 2. 缓存没有查数据库dishListdishMapper.getByStatus(status);// 3. 放入缓存 ← ✅这里触发HashMap的put流程dishCache.put(status,dishList);log.info(从数据库查询菜品状态{},status);}else{log.info(从缓存获取菜品状态{},status);}returndishList;}}4.5面试题-讲一讲HashMap的扩容机制#我的表述 数组不为空扩容 红黑树拆分后扩容 链表超过8,数组长度大于64扩容在添加元素或初始化的时候需要调用resize方法进行扩容第一次添加数据初始化数组长度为16以后每次扩容都是达到了扩容阈值数组长度 * 0.75每次扩容的时候都是扩容之前容量的2倍扩容之后会新创建一个数组需要把老数组中的数据挪动到新的数组中没有hash冲突的节点则直接使用 e.hash (newCap - 1) 计算新数组的索引位置如果是红黑树走红黑树的添加把树拆分成两个小树。拆分后如果小树节点少于6个就变回链表否则保持红黑树如果是链表则需要遍历链表可能需要拆分链表判断(e.hash oldCap)是否为0该元素的位置要么停留在原始位置要么移动到原始位置增加的数组大小这个位置上4.6面试题-hashMap的寻址算法#我的表述 获取值时, 直接找到hash值对应的下标, 在进一步判断key是否相同, 从而找到对应的值 -- 部分正确第一,首先获取key的hashCode值然后右移16位 异或运算 原来的hashCode值, 主要作用是使原来的hash值更加均匀, 减少hash冲突第二,计算数组下标用(n-1) hash代替hash % n。因为位与运算比取模快但要求数组长度必须是2的幂次方。关于hash值的其他面试题为何HashMap的数组长度一定是2的次幂#我的表述 无, 没想到计算索引时效率更高如果是 2 的 n 次幂可以使用位与运算代替取模扩容时重新计算索引效率更高 hash oldCap 0 的元素留在原来位置 否则新位置 旧位置 oldCap4.7面试题-hashmap在1.7情况下的多线程死循环问题#我的表述 hashMap1.8之前采用的是拉链法, 拉链法的意思是数组 链表, 若遇到hash冲突, 则把新增的数据添加到链表中 --只能算做了解jdk1.7, 而不是答案所问因为jdk1.7的hashMap在数组进行扩容的时候, 链表插入采用头插法, 在进行数据迁移的过程中, 则可能导致死循环.(下面例子不懂问AI比如说现在有一个线程A和一个线程B读取hashMap数据进行数组扩容A和B中数组里数据的一个原链表是A → B本来线程1先扩容, 但是线程2抢先完成扩容用头插法把链表变成B → A——即B.next A, A null线程1继续迁移时它先处理A把A放入新链表然后处理B发现B.next指向了A被线程2改的把B插入链表头部后B.next还是指向A然后线程1又去处理AA的next指向B形成循环引用A ↔ B程序卡死当然JDK 8 将扩容算法做了调整不再将元素加入链表头而是保持与扩容前一样的顺序尾插法就避免了jdk7中死循环的问题。4.8面试题-HashSet与HashMap的区别#我的表述 从底层数据结构看 hashSet是集合 hashMap是数组链表/数组红黑树 从数据效率看 hashMap的查找效率是O(1), 而HashSete则是O(n) HashMap和HashSet的插入删除在有数组下标索引时的时间复杂度都是O(1), 如果索引未知, 则时间复杂度都是O(n) 从内存大小看 HashSet存储的是不重复的元素, 而HashMap则是键值对, 会出现采用hashCode的hash值计算数组下标索引, 而数组下标索引相同但key不同, 会插入到链表/红黑树中, 所以会出现更多的数据 从线程安全看 HashSet和HashMap都是非线程安全 --上述表述错误(1)HashSet实现了Set接口, 仅存储对象; HashMap实现了Map接口, 存储的是键值对.(2)HashSet底层其实是用HashMap实现存储的, HashSet封装了一系列HashMap的方法. 依靠HashMap来存储元素值,(利用hashMap的key键进行存储), 而value值默认为Object对象. 所以HashSet也不允许出现重复值, (后面这句话理解麻烦, 用AI进行业务场景描述), 判断标准和HashMap判断标准相同, 两个元素的hashCode相等并且通过equals()方法返回true.4.9面试题-HashTable与HashMap的区别难易程度☆☆出现频率☆☆#我的表述 HashTable实现了Array接口, 存储的是数组, HashMap实现了Map接口, 存储键值对 HashTable的底层是HashMap, HashTable封装了一系列HashMap方法, 用HashMap进行存储, 其hashMap的key键存储, 用value值存储元素值, 所以hashTable存储不允许出现重复值. -- 上述我的表述错误主要区别区别HashTableHashMap数据结构数组链表数组链表红黑树是否可以为nullKey和value都不能为null可以为nullhash算法HashTable直接用key.hashCode()取模HashMap先高16位和低16位异或再用位运算分布更均匀扩容方式当前容量翻倍 1当前容量翻倍线程安全同步(synchronized)的线程安全非线程安全在实际开发中不建议使用HashTable在多线程环境下可以使用ConcurrentHashMap类实际场景上面表格表述 如下表述第一, 数据结构, HashTable是数组 链表, 而HashMap是数组 链表 / 数组 红黑树第二, 是否可以为null, HashTable的key和value不可以为null, 而HashMap的键值对可以为null第三, Hash算法, HashTable是用hashCode计算, 再取模, 而HashMap是高16位与低16位异或, 然后再位运算, 使哈希分布更均匀.第四, 数组扩容, HashTable是原先翻倍1, 而HashMap是原先翻倍第五, 线程安全, HashTable是同步synchronized, 是线程安全的, 而HashMap是非线程安全的.所以在实际开发中不建议使用HashTable, 而在多线程环境下使用ConcurrentHashMap.