一、数据结构
顺序存储：
- 性质：连续的存储单元来存储数据（逻辑上连续，物理上也连续）
- 特点：随机存取。适合查找，不适合增删；更节约空间
链式存储：
- 性质：非连续的存储单元来存储数据（逻辑上连续，物理上不一定连续）
- 特点：非随机存取。适合增删，不合适查找；有指针域，空间利用率比顺序存储低
索引存储：
- 性质：通过增加索引（相当于书的目录），来检索目标，一般使用B+树实现
- 特点：检索快，插入慢。费空间
- 延伸：B+树和B-树的最主要区别之一是B+树只有叶子节点才存储data信息，而B-树在其他节点也存储信息
- 注意：B树就是B-树，B-tree（balance-tree，平衡树）
哈希/散列存储：
- 性质：通过哈希函数计算出key的哈希值并找到存储位置，然后定位目标。存储位置index = f（key）
- 特点：检索快。可能有哈希冲突要解决
- 构建哈希函数：直接寻址，除数取余等
- 解决哈希冲突：开放寻址（a、线性探查；b、平方探查），链地址/拉链法（hashmap采用此法，数组+链表）等
- 注意：哈希表的主干是数组，利用其可以随机存取特性；如用链地址法，则还有链表分支
注意：数据的逻辑结构可以用多种不同的存储结构表示
二、HashMap
HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
产生链表的原因：不同的key经过hash函数得到相同的hash值。所以需要保证，相同key对象，hash值一定相等，但是不同的key对象，可能有相同的hash值
重要知识点
-
负载因子：默认是0.75，一般在0.6-0.9之间比较好，可以减少哈希冲突。如 已存元素/内存空间 >= 负载因子，则空间会扩容一倍
-
存储下标：生成过程如下图
-
为什么HashMap数组长度是2的幂次方？a，扩容只是左边增加一位，保证新老数组一致性；b，可以保证index分布均匀；c，可以最大化利用数组
-
为什么重写equals()要重写hashcode()方法？因为在生成存储下标的时候调用了hashcode()方法，默认的hashcode()方法继承自Object类的native hashcode()方法，而此方法是java调用的C++底层实现，用于获取对象的存储地址。如果只重写equals()方法，那么会出现对象内容一致但是存储位置不一致的情况而导致无法精确匹配。重写hashcode（）方法在于人为控制内容一致的对象有相同的hashcode码。
Object的hashCode()方法
HashMap的put()方法
public V put(K key, V value) {
//如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，
//此时threshold为initialCapacity 默认是1<<4(左位移4，2的4次方=16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//如果key为null，存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
int i = indexFor(hash, table.length);//获取在table中的实际位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 先判断hash值是否一致，如果一致，再判断key值是否相等。如果hash值一致，则不需要再进行key值的equals的判断，可以提高效率。
// 如果重写了equals()方法，则需要重写hashcode()方法。因为key生成hash码时，先调用了hashcode()方法。默认的hashcode()方法继承自Object的native hashcode()方法，而此方法是java调用的C++底层实现，用于获取对象的存储地址。如果只重写equals()方法，那么会出现key对象内容一致但是存储位置不一致的情况而无法精确匹配。重写hashcode()方法以保证相同内容的key对象有相同的hashcode值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
addEntry(hash, key, value, i);//新增一个entry
return null;}
HashMap的hash()方法
对key对象的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// 调用了hashCode()函数，重写此函数以保证相同的key对象有相同的hashCode值
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
参考：https://blog.csdn.net/woshimaxiao1/article/details/83661464