-
如果该索引位置元素对应的hash值和待插入的元素的hash值相同，且是同一个引用或者是内容相同的话就不能添加
-
如果索引位置有值且满足一颗红黑树的话，则调用红黑树的算法进行添加
-
如果索引位置有值且是一个链表的话，则循环比较链表，如果存在相同元素的话，则不允许添加，否则添加到链尾即可
//1.执行HashSet()
public HashSet() {
map = new HashMap<>();
}
//2.执行add()
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
//3.执行put()
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//对hash值进行无符号右移16位，防止冲突
}
//4.执行putVal()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//tab其实HashMap的一个数组，类型是 Node[],第一次扩容，到16个空间
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根据Key得到一个hash值，然后计算该key在tab中所对应的索引下标，并把这个索引对应的元素赋给p
//if p == null 表示该位置还没有存放元素，就创建一个Node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//判断当前添加的对象的引用或者内容是否相同，前提是他们的hash值要相同，如果满足条件的话则不嫩加入
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//否则再判断是否是一颗红黑树，如果是一颗红黑树，则采用红黑树的算法进行
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//否则如果是一个链表，则依次循环比较，如果找到相同的就退出，否则把当前对象放在尾部即可
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
[](
)LinkedHashSet
LinkedHashSet 底层是一个LInkedHashMap,底层维护了一个数组+双向链表
LInkedHashSet根据元素的HashCode值来决定元素的位置，同时使用链表维护元素的次序，这使得元素看起来是以插入的顺序保存的
LInkedHashSet 不允许添加重复元素
[](
)Map集合
Map与Collection并列存在。用时于保存具有映射关系的数据:Key-Value
Map中的key 和value可以是任何引用类型的数据，会封装到HashMap $Node对象中
Map中的key 不允许重复，原因和HashSet一样，前面分析过源码,Map 中的value可以重复
Map 的key可以为null, value 也可以为null，注意key为null,只能有一个，value为null ,可以多个
常用String类作为Map的key,但并不是所有只能用String作为key,kev和value之间存在单向一对一关系，即通过指定的 kev总能找到对应的value
k-v形式最终会是 HashMap $Node node = newNode(hash， key,value,null)
k-v为了方便程序员的遍历，还会创建 EntrySet集合，该集合存放的元素的类型 Entry，而一个Entry对象就有k,v ，EntrySet<Entry<K,V>>即:transient Set<Map. Entry<K,V>> entrySet;
entrySet中，定义的类型是 Map.Entry ，但是实际上存放的还是 HashMap $Node
这是因为static class Node<K,V> implements Map.Entry<K, V>，当把 HashMap $Node对象存放到entrySet时就方便我们的遍历
[](
)Map 接口的遍历方式
-
通过keySet获取map里所有的键，获取键后返回一个集合，可采用集合的遍历增强for或者迭代器 iterator进行遍历
-
通过values获取所有的value集合，可通过集合的方式遍历
-
通过entrySet获取所有的关系k-v,可通过集合的遍历
[](
)HashMap
HashMap底层维护了Node类型的数组table，默认为null
当创建对象时，将加载因子(loadfactor)初始化为0.75.
当添加key-val时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素,如果没有元素直接添加。如果该索引处有元素,继续判断该元素的key和准备加入的key相是否等,如果相等，则直接替换val;如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。
第1次添加，则需要扩容table容量为16，临界值(threshold)为12(16*0.75)
以后再扩容，则需要扩容table容量为原来的2倍(32)，临界值为原来的2倍,即24.依次类推
在Java8中,如果一条链表的元素个数超过 TREEIFY_THRESHOLD(默认是8)，table的大小 >= MIN_TREEIFY_ CAPACITY(默认64),就会进行树化(红黑树)
源代码分析及结论
同HashSet一样，因为HashSet底层是HashMap
[](
)Hashtable
存放的元素是键值对:即K-V
hashtable的键和值都不能为null，否则会抛出NullPointerException3) hashTable使用方法基本上和HashMap一样
hashTable是线程安全的(synchronized), hashMap是线程不安全的
源代码分析及结论：
-
Hashtable底层维护的也是一个数组Hashtable$Entry[] 初始化大小为11
-
临界值等于11*0.75 =8
-
扩容机制：当加入的数量到达临界值是，扩容量为原来的2倍+1，即：newCapacity = (oldCapacity << 1) + 1;
-
当加入相同相同key对应的value时，则进行value替换
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;//扩容机制
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
关于Hashtable和HashMap的对比：
| | 版本 | 线程安全（同步） | 效率 | 允许null键null值 |
| :-: | :-: | :-: | :-: | :-: |
| Hashtable | 1.0 | 安全 | 不高 | 不允许 |
| HashMap | 1.2 | 不安全 | 高 | 允许 |
[](
)Properties
-
Properties类继承自Hashtable类并且实现了Map接口，也是使用一种键值对的形
式来保存数据，他的使用特点和Hashtable类似
-
Properties 还可以用于从 xxx.properties 文件中，加载数据到Properties类对象,
并讲行卖取和修改
相关知识点：https://www.cnblogs.com/xudong-bupt/p/3758136.html
[](
)TreeSet
TreeSet底层实际上是TreeMap
可排序(可安自定义的方式进行排序输出，底层插入顺序和取出顺序一致，不是add的顺序，是经过比较器计算后的顺序)
源代码分析及结论：
-
当使用无参构造创建一个对象是，会默认将key转成比较器对象（前提是该key必须实现Comparable且实现了compareTo方法），使用默认的compareTo方法进行自然排序
-
当使用有参构造时，需要传入一个含有compare方法的比较器对象，然后TreeSet底层会将其封装给TreeMap对象中的comparator，底层加入是会自动调用该方法进行排序
-
如果TreeSet存放的是Integer对象，默认排序方法为 小到大；
-
如果TreeSet存放的是String对象，默认排序方法为字符串首字母开始比较，按Unicode值大小排序；
-
如果TreeSet存放的是自定义类；如果不指定指定比较器，那么就会报异常；
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check//第一次添加的时候调用比较，判断是不是能进行比较
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);//传入的比较器对象，含有自定义的compare方法
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;//默认比较方法，前提是key必须实现Comparable接口
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
> **Java网盘：pan.baidu.com/s/1MtPP4d9Xy3qb7zrF4N8Qpg
> 提取码：2p8n**
# 总结
在这里，由于面试中MySQL问的比较多，因此也就在此以MySQL为例为大家总结分享。但是你要学习的往往不止这一点，还有一些主流框架的使用，Spring源码的学习，Mybatis源码的学习等等都是需要掌握的，我也把这些知识点都整理起来了
**[CodeChina开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频】](
)**
uper K> k = (Comparable<? super K>) key;//默认比较方法，前提是key必须实现Comparable接口
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
> **Java网盘：pan.baidu.com/s/1MtPP4d9Xy3qb7zrF4N8Qpg
> 提取码：2p8n**
# 总结
在这里，由于面试中MySQL问的比较多，因此也就在此以MySQL为例为大家总结分享。但是你要学习的往往不止这一点，还有一些主流框架的使用，Spring源码的学习，Mybatis源码的学习等等都是需要掌握的，我也把这些知识点都整理起来了
**[CodeChina开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频】](
)**
[外链图片转存中...(img-Iqgk3IB7-1631407615946)]
