Java基础知识【HashMap和Hashtable区别与红黑树】

1. HashMap和HashTable

相同点

1. 两者都是基于哈希表实现的，同样每个元素是一个key-value对，其内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。
2. 两者都实现了Serializable接口和Cloneable接口，支持序列化和克隆。

区别:

1. HashMap方法没有synchronized修饰,线程非安全，HashTable线程安全;
2. HashMap允许key和value为null,而HashTable不允许
3. Hashtable是线程安全，而HashMap则非线程安全。Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步。
4. HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口，能被克隆。

底层实现:数组+链表实现

jdk1.8开始链表高度到8、数组长度超过64.链表转变为红黑树，元索以内部类Node节点存在

• 计算key的hash值，二次hash然后对数组长度取模，对应到数组下标，
• 如果没有产生hash冲突(下标位置没有元索)，则直接创建Node存入数组,
• 如果产生hash冲突，先进行equal比较，相同则取代该元素，不同，则判断链表高度插入链表,链表高度达到 8,并且数组长度到 64 则转变为红黑树，长度低于 6 则将红黑树转回链表
• key为null, 存在下标0的位置

2. HashMap和 HashSet

1. HashMap实现了Map接口(底层实现:数组+链表实现)，而HashSet实现了Set接口。
2. HashMap用于存储键值对，而HashSet用于存储对象。
3. HashMap不允许有重复的键，可以允许有重复的值。HashSet不允许有重复元素。
4. HashMap允许有一个键为空，多个值为空，HashSet允许有一个空值。
5. HashMap中使用put()将元素加入map中，而HashSet使用add()将元素放入set中。
6. HashMap比较快，因为其使用唯一的键来获取对象。

3. 红黑树

红黑树具体规则特点，如下所示：

• 节点分为红色或者黑色。
• 根节点必为黑色。
• 叶子节点都为黑色，且为 null。
• 连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）。
• 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点。
• 新加入到红黑树的节点为红色节点。