什么是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冲突,图示:
网络异常,图片无法展示
|
参考:
https://blog.csdn.net/m0_37499059/article/details/80623438
https://www.cnblogs.com/lyfstorm/p/11044468.html