共计 4513 个字符，预计需要花费 12 分钟才能阅读完成。
1. 罕用的实现类构造
一、HashMap
实现了 Map、Cloneable、Serializable 接口，继承了 AbstractMap 类
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
/**
* Map 接口: 实现键值对,Map 接口规定了一个 key 对应一个 value
* HashMap 应用该接口用来替换 Dictionary 类
*
* AbstractMap 类: 继承 Map 的抽象类, 缩小 Map 操作的实现
*
* Cloneable 接口: 能够显示的调用 Object.clone()办法, 非法的对该类
* 实例进行字段复制
*
* Serializable 接口: 实现该接口后, 该类能够被序列化和反序列化
*/1.HashMap 是否线程平安？
HashMap 是线程不平安的，在并发的环境下能够应用 ConcurrentHashMap。
2.HashMap 的外部实现
外部实现：在 JDK1.8 之前是数组 + 链表，JDK1.8 之后是数组 + 链表 + 红黑树
退出红黑树的起因:JDK1.8 之前 HashMap 应用的是数组加链表，因为哈希函数不能百分百的让元素平均的散布，就会造成有大量的元素存入同一个 index（桶）下，这样 index 就造成了一条很长的链表，由此元素的遍历的工夫复杂度为 O(n), 失去了 HashMap 的劣势，退出了红黑树，查找的工夫复杂度为 O(log n), 实现了优化
数组的特点：查找快，工夫复杂度是 O(1), 增删慢，工夫复杂度是 O(n)
链表的特点：查找慢，工夫复杂度是 O(n), 增删快，工夫复杂度是 O(1)
红黑树的特点：在遍历链表的根底上，红黑树查找的工夫复杂度是 O(log n)
红黑树的查问效率远大于链表，然而插入 / 删除要比链表慢
3.HashMap 的主要参数
1. 默认初始容量：16，必须是 2 的整数次方
2. 默认加载因子：0.75
3. 阈值：容量 * 加载因子
4. 树形阈值：默认是 8，当 bucket 中的链表长度大于 8 时，则进行链表树化
5. 非树形阈值：默认是 6，当进行扩容时，当进行扩容（resize（））时（这时候的 HashMap 的数据存储地位会从新计算），在计算完后，原有的红黑树内的数量 <6 时，则由红黑树转换为链表
6. 树形最小容量：桶可能是树的哈希表的最小容量，至多是 TREEIFY_THRESHOLD 的 4 倍，这样能防止扩容时的抵触
// 链表转红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才容许树形化链表（即 将链表 转换成红黑树）* 否则，若桶内元素太多时，则间接扩容，而不是树形化
* 为了防止进行扩容、树形化抉择的抵触，这个值不能小于 4 * TREEIFY_THRESHOLD
**/
static final int MIN_TREEIFY_CAPACITY = 64;只有在数组的长度大于 64 时，且链表的长度 >8 时，能力树形化链表
链表的长度大于 8 时会调用 treeifyBin 办法转换为红黑树，然而 treeifyBin 办法外部有一个判断，当只有数组的长度 >64 的时候，能力将链表树形化，否则只进行 resize 扩容
因为链表过长而数组过短，会常常产生 hash 碰撞，这时进行树形化的作用不大，因为链表过长的起因就是数组过短。树形化之前要查看数组的长度，<64 进行扩容，而不是进行树形化
链表的长度 >8，但数组的长度 <64 时, 不会进行树形化，而是进行 resize 后 rehash 从新排序
4.HashMap 的罕用办法
增加：V put(K key,V value) –> 增加元素（也能够实现批改）
删除：void clear() –> 清空所有键值对元素
V remove(Object key) –> 依据键删除对应的值，并把值返回
判断：containsKey(Object key) –> 是否蕴含指定的键
containsValue(Object value)–> 是否蕴含指定的值
遍历：Set<Map.Entry<K,V>> entrySet()–> 获取键值对
V get(Object key) –> 依据键获取值
Collection value()–> 获取值的汇合
获取：Set setKey()–> 获取键的汇合
int size()–> 获取汇合元素的个数
根本办法的应用
HashMap<Integer,String> map=new HashMap<>();
// 增加元素
map.put(1, "a");
map.put(2, "b");
map.put(3, "c");
// 键不可反复，值被笼罩
map.put(3, "C");
// 通过键删除整个键值对
map.remove(3);
// 清空
map.clear();
// 是否为空
System.out.println(map.isEmpty());//false
// 是否蕴含 4
System.out.println(map.containsKey(4));//false
// 是否蕴含“b”值
System.out.println(map.containsValue("b"));//true
// 获取汇合元素个数
System.out.println(map.size());//3
// 通过键获取值
System.out.println(map.get(3));//C
// 获取所有值形成的汇合
Collection<String> values=map.values();
for(String v:values){System.out.println("值:"+v);// 值：a 值：b 值：c
}
System.out.println(map);
}两种遍历形式
public static void main(String[] args) {Map<String,Integer> map=new HashMap<>();
map.put("小林",21);
map.put("小张",35);
map.put("小王",18);
demo1(map);
demo2(map);
}
// 通过 Set<K> setKey()办法遍历
private static void demo1(Map<String,Integer> map) {Set<String> keys=map.keySet();
for (String key:keys){Integer value=map.get(key);
System.out.println("键为："+key+"值为："+value);// 键为：小林值为：21
// 键为：小王值为：18
// 键为：小张值为：35
}
}
// 通过 Set<Map.Entry<K,V>> entrySet()办法遍历
private static void demo2(Map<String, Integer> map) {Set<Map.Entry<String,Integer>> kvs=map.entrySet();
for (Map.Entry<String,Integer> kv:kvs){String kstring=kv.getKey();
Integer istring=kv.getValue();
System.out.println(kstring+"-----"+istring);
// 小林 -----21
// 小王 -----18
// 小张 -----35
}
}5. 对于 hash 抵触问题
1. 起因：
当对某个元素进行哈希运算后，失去一个存储地址，在进行插入的时候，发现曾经被其余元素占用了。这就是所谓的哈希抵触，也叫哈希碰撞。
哈希函数的设计至关重要，好的哈希函数会尽量的确保计算简略和散列地址散布平均，然而，数组是一块间断的固定的长度的内存空间，再好的哈希函数也不能保障失去的存储地址相对不发生冲突。
2. 解决 hash 抵触的办法：
凋谢地址法：发生冲突，持续寻找下一块未被占用的存储地址。
再散列函数法：当发生冲突，应用第二个、第三个、哈希函数计算地址，直到无抵触。
链地址法：将所有关键字的同义词的记录存储在一个单链表中，咱们称这种表为同义词子表。
HashMap 采纳的是链地址法，也就是数组 + 链表的形式
HashMap 由数组 + 链表组成的，数组是 HashMap 的主体，链表则是次要为了解决哈希抵触而存在的，如果定位到的数组地位不含链表（以后的 entry 的 next 指向 null），那么对于查找，增加等操作很快，仅需一次寻址即可；如果定位到的数组蕴含链表，对于增加操作，其工夫复杂度为 O(n), 首先遍历链表，存在即笼罩，否则新增，而后通过 key 对象的 equals 办法逐个比对查找。所以！对于性能思考，HashMap 中的链表呈现越少，性能才会越好。
6.JDK1.8 之前 HashMap 存在死循环的问题
起因：因为数组扩容后，同一索引地位的节点程序会反掉
7.HashMap 和 Hashtable 的区别
8. 重写 equals()办法后，是否肯定要重写 hashCode()办法？为什么？
重写 equals()办法，须要重写 hashCode()办法。
hashCode 规定：两个对象相等（即 equals()返回 true），hashCode 肯定雷同；两个对象 hashCode 雷同，两个对象不肯定相等；
重写 equals，而不重写 hashCode 办法，默认调用的是 Object 类的 hashCode()办法，会导致两个对象的 equals 雷同但 hashCode 不同。简略的来说，重写 equals 办法后，重写 hashCode 办法就是为了确保比拟的两个对象是同一对象。
二、LinkedHashMap
LinkedHashMap 的底层构造和 HashMap 是雷同的，因为 LinkedHashMap 继承了 HashMap，
区别在于：LinkedHashMap 外部提供了 Entry，替换了 HashMap 中的 Node。
LinkedHashMap：保障在遍历 map 元素时，能够照增加的程序实现遍历
起因：在原来的 HashMap 底层构造的根底上，减少了一对指针，指向前一个和后一个元素
对于频繁的遍历操作，LinkedHashMap 的效率要高于 HashMap
三、TreeMap
保障照 key-value 对进行排序，实现排序遍历，此时思考 key 的天然排序或者定制排序，底层应用的是红黑树
元素依据键排序，元素具备唯一性
1）天然排序
让元素所在的类继承天然排序 Comparable
2）比拟器排序
让汇合的构造方法接管一个比拟器接口（Comparator 的实现对象）
四、Hashtable
作为古老的实现类；线程平安的，效率低；不能存储 null 的 key 和 value
最初
大家看完有什么不懂的能够在下方留言探讨，也能够关注我私信问我，我看到后都会答复的。也欢送大家关注我的公众号：前程有光，金三银四跳槽面试季，整顿了 1000 多道将近 500 多页 pdf 文档的 Java 面试题材料，文章都会在外面更新，整顿的材料也会放在外面。谢谢你的观看，感觉文章对你有帮忙的话记得关注我点个赞反对一下！
