什么是HashMap？
探讨HashMap之前我们要理清楚一个概念：哈希表
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
然后是HashMap的概念
基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。
解决哈希冲突的常用方法
为什么会产生哈希冲突？
如何解决哈希冲突？
- 开放定址法：
所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入 - 再哈希法：
再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数
计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。 - 链地址法：
链地址法的基本思想是：每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向 - 建立公共溢出区：
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表
手写HashMap
/** * @desc: HashMap的简单实现 * @author: YanMingXin * @create: 2021/8/9-9:46 **/ public class MyHashMap<K, V> { /** * 默认容量16 */ private final int DEFAULT_CAPACITY = 16; /** * 内部存储结构 */ private Node[] table = new Node[DEFAULT_CAPACITY]; /** * 长度 */ private int size = 0; /** * keySet */ private Set<K> keySet; /** * 获取大小 * * @return */ public int size() { return this.size; } /** * 判断是否为空 * * @return */ public boolean isEmpty() { return size == 0; } /** * get方法 * * @param key * @return */ public Object get(Object key) { int hashValue = hash(key); int i = indexFor(hashValue, table.length); for (Node node = table[i]; node != null; node = node.next) { if (node.key.equals(key) && hashValue == node.hash) { return node.value; } } return null; } /** * put方法 * * @param key * @param value * @return */ public Object put(Object key, Object value) { //通过key,求hash值 int hashValue = hash(key); //通过hash,找到这个key应该放的位置 int i = indexFor(hashValue, table.length); //i位置已经有数据了，往链表添加元素 for (Node node = table[i]; node != null; node = node.next) { Object k; //且数组中有这个key,覆盖其value if (node.hash == hashValue && ((k = node.key) == key || key.equals(k))) { Object oldValue = node.value; node.value = value; //返回oldValue return oldValue; } } //如果i位置没有数据，或i位置有数据，但key是新的key,新增节点 addEntry(key, value, hashValue, i); return null; } /** * 增加节点 * * @param key * @param value * @param hashValue * @param i */ public void addEntry(Object key, Object value, int hashValue, int i) { //如果超过了原数组大小，则扩大数组 if (++size == table.length) { Node[] newTable = new Node[table.length * 2]; System.arraycopy(table, 0, newTable, 0, table.length); table = newTable; } //的到i位置的数据 Node eNode = table[i]; //新增节点，将该节点的next指向前一个节点 table[i] = new Node(hashValue, key, value, eNode); } /** * 获取插入的位置 * * @param hashValue * @param length * @return */ public int indexFor(int hashValue, int length) { return hashValue % length; } /** * 获取hash值 * * @param key * @return */ public int hash(Object key) { return key.hashCode(); } /** * toString方法 * * @return */ @Override public String toString() { ArrayList list = new ArrayList<Node>(); for (Node node : table) { if (node != null) { list.add(node); } } return list.toString(); } /** * 静态内部类 */ static class Node<V> { int hash;//hash值 Object key;//key Object value;//value Node<V> next;//指向下个节点（单例表） Node(int hash, Object key, Object value, Node<V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public Object getKey() { return this.key; } public Object getValue() { return this.value; } @Override public String toString() { return "{" + key + ", " + value + "}"; } } }
在本次HashMap的实现中就使用到了链地址法解决hash冲突，图示：
