存储原理
数组是最基本的数据结构，ArrayList内部就是数组实现的，下标定位位置，然后在数组下标位置存放元素，每添加一个元素，下标就 1，map和list有一点相似，就是内部也有个数组， 它通过key存放获取对象，以key计算数组下标。使用hashCode的话，得出的值很大，很容易是数组越界，可以使用取余的方式减小这个，那么余多少呢？比如下标是0-7，那么我们可以余它的数组大小（length），hashCode是随机的，得出的下标也是随机的，这也使得数组下标随机平均。
但还有一个问题，hashCode是随机的，但在取余之后得到的值很可能是相同的，比如第一次你存了kk1: vv1，第二次存放kk2: vv2计算key后得出的位置也是同一个位置，那么在同一下标有两个对象了，那么可以链表去解决这个问题；再来一个，也是计算得到同一个下标，考虑一个问题，是插入头部比较快还是尾部比较快？
如果是头插法，只需要修改新节点的next的下一个节点指针就行了，而如果是尾插，那么还需要遍历链表，然后修改尾部的指针，显然，尾插法的效率不是很高，map里就是用的头插法，头插法只有next的元素，这是查找下一个元素使用的，它没有向上查找的方式，它的查找方式也是先计算数组下标，得到下标后，找到对应的链表，然后遍历的：
上面只是对map的一个原理说明，并不严谨。
源码解析
这里从HashMap的源码上去看HashMap这个结构，从源码分析理解。
HashMap里有这些个属性：
代码语言：javascript复制 // 默认初始容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 空数组对象
static final Entry<?,?>[] EMPTY_TABLE = {};
// 内部数组，
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// map长度
transient int size;
// 阈值，是否扩容根据这个判断：threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY 1) => capacity * loadFactor
int threshold;
// 加载因子，扩容计算用到
final float loadFactor;
// 修改计数
transient int modCount;
// hash种子，计算hash值用到，为了是计算的hashCode更加的散列随机。
transient int hashSeed = 0;Entry<K,V>[] 的定义里有这么几个属性，只有next，没有向前查找的对象，所以遍历，只能从头往下遍历。
代码语言：javascript复制final K key;
V value;
// 指向下一个对象
Entry<K,V> next;
int hash;构造行数从put方法开始看：
代码语言：javascript复制public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// key == null 的情况
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount ;
addEntry(hash, key, value, i);
return null;
}put方法一进来就是这个，初始化内部数组
代码语言：javascript复制 if (table == EMPTY_TABLE) {
inflateTable(threshold);
}进入inflateTable方法，首先它有一个计算容量的方法roundUpToPowerOf2，然后计算阈值threshold，然后是计算哈希种子。
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}跟进：
代码语言：javascript复制 private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}上面这一串就需要看：
代码语言：javascript复制 Integer.highestOneBit((number - 1) << 1) public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}这个是计算小于等于当前值的二次方数，比如下面给定值为17，其结果是16，给定值是18,19,20都会是16，
代码语言：javascript复制i=17 =>
0000 0000 0000 0000 0000 0000 0001 0001
(i >> 1) =>
0000 0000 0000 0000 0000 0000 0000 1000
i |= (i >> 1) =>
0000 0000 0000 0000 0000 0000 0001 1000
...
i |= (i >> 16) =>
0000 0000 0000 0000 0000 0000 0001 1111
i - (i >>> 1) =>
0000 0000 0000 0000 0000 0000 0001 1111
0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0001 0000roundUpToPowerOf2注释写着要2的每次方数，那为什么要2的幂次方数呢？
可以看看这篇博客： https://blog.csdn.net/LLF_1241352445/article/details/81321991?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase
其结论就是：用位运算取余，还有就是计算出的数组下标更加散列平均。
了解了highestOneBit方法后，再看上一层代码，为什么要-1，和左移1位？
Integer.highestOneBit((number - 1) << 1)原因是
- 我们要得到的是一个大于等于在给定值的一个2的幂次方数，
highestOneBit得到的是一个小于等于给定值的幂次方数，所以左移1位；假如我们给定值为17，那么要得到的结果应该是32，如果我们不左移，最后得到的值肯定是16 - 假如给定值是16，要得到结果应该是16，左移1位得到32，所以左移前-1得到15，在左移得到30才能得到16
返回put方法有一段：
代码语言：javascript复制 if (key == null)
return putForNullKey(value); private V putForNullKey(V value) {
// 遍历内部数组的第0个位置的链表，查找是否有key == null的键，如果有就返回旧值
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
// 这个方法不管他，跟hashMap没有关系，这个是给它子类（LinkedHashMap）写的。
e.recordAccess(this);
return oldValue;
}
}
modCount ;
addEntry(0, null, value, 0);
return null;
}再回到put方法：
代码语言：javascript复制public V put(K key, V value) {
if (table == EMPTY_TABLE) {
// 初始化数组
inflateTable(threshold);
}
// 第一种情况key == null
if (key == null)
return putForNullKey(value);
// 计算hash值
int hash = hash(key);
// 这里就是hash & (table.length - 1)
// 计算数组下标
int i = indexFor(hash, table.length);
// 遍历数组下标对应的链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 判断key计算的hash值相同，且key值相同
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 设置新值，获取旧值并返回
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 每次修改 1
modCount ;
// 如果没有找的对应的，就新增一个
addEntry(hash, key, value, i);
return null;
}modCount这个标识是一种快速失败的机制，可以这样理解，多线程下，一个线程在遍历，一个线程在新增或删除，遍历了一般，元素被删除了，在遍历的时候就会出现问题，取值、个数都不对了，所以必须抛一个异常结束这个错误操作。
代码语言：javascript复制 void addEntry(int hash, K key, V value, int bucketIndex) {
// 判断数组大小是否大于等于阈值 且要添加的位置有元素
if ((size >= threshold) && (null != table[bucketIndex])) {
// 扩容方法
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}就看看数组元素转移的方法，其他比较简单就是赋值
代码语言：javascript复制 void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历就数组
for (Entry<K,V> e : table) {
// 遍历每一个元素下的链表
while(null != e) {
Entry<K,V> next = e.next;
// 重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 计算数组下标
int i = indexFor(e.hash, newCapacity);
// 转移到新数组
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}而get方法相对简单些
代码语言：javascript复制 public V get(Object key) {
if (key == null)
// key == null 的情况
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
} private V getForNullKey() {
if (size == 0) {
return null;
}
// 遍历数组第一个位置的链表
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
// 找到key == null 的元素并返回
if (e.key == null)
return e.value;
}
return null;
}final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
// 计算位置
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// 判断hash值、key相同并返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
