Java进阶-哈希表数据结构

HashMap 集合底层是哈希表/散列表的数据结构
哈希表是一个怎样的数据结构呢？
- 哈希表是一个数组和单向链表的结合体
- 数组：在查询方面效率很高，随机增删方面效率很低
- 单向链表：在随机增删方面效率很高，在查询方面效率很低
- 哈希表将以上的两种数据结构融合在一起，充分发挥它们各自的优点

HashMap 集合底层的源代码

public class HashMap {
  // HashMap 底层实际上就是一个数组（一维数组）
  Node<K, V>[] table;
  
  // 静态的内部类 HashMap.Node
  static class Node<K, V> {
    final int hash; // 哈希值（key的hashCode()方法的执行结果。hash值通过哈希函数/算法，可以转换存储成数组的下标）
    final K key; // 存储到Map集合中的那个key
    V value; // 存储到Map集合中的那个value
    Node<K, V> next; // 下一个节点的内存地址
  }
}

哈希表/散列表：一维数组，这个数组中每一个元素是一个单向链表（数组和链表的结合体）

最主要掌握的是（实现原理）：
- map.put(k, v)
- v = map.get(k)

HashMap 集合的 key 部分特点：

无序，不可重复
为什么无序？
- 因为不一定挂到哪个单向链表上
不可重复怎么保证？
- equals 方法保证 HashMap 集合的 key 不可重复，如果 key 重复了，value 会覆盖

放在 HashMap 集合 key 部分的元素其实就是放到了 HashSet 集合中，所以 HashSet 集合中的元素也需要同时重写 hashCode()、equals() 方法

import java.util.HashMap;
import java.util.Map;

public class HashMapTest01 {

	public static void main(String[] args) {
		// 测试 HashMap 集合 key 部分的元素特点
		// Integer 是 key，它的 hashCode 和 equals 重写了
		Map<Integer, String> map = new HashMap<>();
		map.put(111, "zhangsan");
		map.put(666, "lisi");
		map.put(777, "wangwu");
		map.put(222, "zhaoliu");
		map.put(222, "king"); // key 重复的时候value会自动覆盖

		System.out.println(map.size()); // 4
	}
}

哈希表 HashMap 使用不当时无法发挥性能
- 假设将所有的 hashCode() 方法返回值固定为某个值，那么会导致底层哈希表变成了纯单向链表，这种情况我们称为：散列分布不均匀
- 什么是散列分布均匀？
  - 假设有100个元素，10个单向链表，那么每个单向链表上有10个节点，是最好的，是散列分布均匀的
- 假设将所有 hashCode() 方法返回值都设定为不一样的值，有何问题？
  - 会导致底层哈希表变成一维数组，没有链表的概念了，也是散列分布不均匀
- 散列分布均匀需要重写 hashCode() 方法时有一定的技巧
HashMap 集合的默认初始化容量是16，默认加载因子是 0.75
- 默认加载因子：当 HashMap 集合底层数组的容量达到 75% 的时候，数组开始扩容
- 重点：HashMap 集合初始化容量必须是 2 的倍数，这也是官网推荐的。为了达到散列均匀，提高 HashMap 集合的存取效率