Hash 碰撞问题和手写HashMap
原创
前言
接着上面一篇讲述了 Hash 与 Hash表 与 HashCode、HashMap 数据结构、HashMap 的容量 下面我们继续说说碰撞和手写实现一下
Hash 碰撞问题
什么是 Hash 碰撞
- 通过 hash 方法操作后，得到了两个相同的结果
- 在我们这里，我们对 HashCode 值进行
%16，有可能两个对象取模的结果是一样的 - 因为有
Hash碰撞，数组的利用率很难达到100%
img
解决 Hash 碰撞
为了解决 Hash 碰撞，在里面引入了链表，采用了 头 插入链表的方式。
img
链表的时间复杂度为 O(n)。
手写 HashMap
定义接口与实现
基础接口
创建 MyMap 接口内容如下
/**
* @author yby6
**/
public interface MyMap<K, V> {
/**
* 添加元素
*
* @param k k
* @param v v
* @return {@link V}
*/
V put(K k, V v);
/**
* 获取元素
*
* @param k k
* @return {@link V}
*/
V get(K k);
interface Entry<K, V> {
/**
* 获取Key
*
* @return {@link K}
*/
K getKey();
/**
* 获取Value
*
* @return {@link V}
*/
V getValue();
}
}创建所对应的 MyHashMap 实现类内容如下
/**
* @author yby6
**/
public class MyHashMap<K, V> implements MyMap<K, V> {
@Override
public V put(K k, V v) {
return null;
}
@Override
public V get(K k) {
return null;
}
/**
* @author yby6
*/
class Entry<K, V> implements MyMap.Entry {
@Override
public K getKey() {
return null;
}
@Override
public V getValue() {
return null;
}
}
}PUT 方法实现
/**
* @author yby6
**/
public class MyHashMap<K, V> implements MyMap<K, V> {
/**
* 定义存储元素数组
*/
private Entry<K, V>[] table = null;
public MyHashMap() {
this.table = new Entry[16];
}
private int size = 0;
public int size() {
return size;
}
@Override
public V put(K k, V v) {
// 1.获取k的hashcode%16 = hash值 对应数组当中的位置
int hashValue = hash(k);
// 2.判断数组当中对应位置有没有元素
Entry<K, V> entry = table[hashValue];
if (null == entry) {
// 没有元素,直接存储 Entry<K,V>
table[hashValue] = new Entry<>(k, v, hashValue, null);
size++;
} else {
// 更新
if (table[hashValue].k.equals(k)) {
table[hashValue].v = v;
} else {
// 如果有元素,有hash碰撞,就要把数据使用头插法 插入到链表的头部,记录原来的值
table[hashValue] = new Entry<>(k, v, hashValue, entry);
size++;
}
}
return table[hashValue].getValue();
}
/**
* 哈希
*
* @param k k
* @return int
*/
private int hash(K k) {
int index = k.hashCode() % 16;
return index > 0 ? index : -index;
}
@Override
public V get(K k) {
return null;
}
/**
* @author yby6
*/
class Entry<K, V> implements MyMap.Entry {
/**
* k
*/
K k;
/**
* v
*/
V v;
/**
* 哈希
*/
int hash;
/**
* 下一个节点元素
*/
Entry<K, V> next;
/**
* HashMap元素
*
* @param k k
* @param v v
* @param hash 哈希值
* @param next 下一个节点元素
*/
public Entry(K k, V v, int hash, Entry<K, V> next) {
this.k = k;
this.v = v;
this.hash = hash;
this.next = next;
}
@Override
public K getKey() {
return this.k;
}
@Override
public V getValue() {
return this.v;
}
}
}如上 Entry 内部类的 getKey、getValue 就直接返回对应的属性值即可，接下来就是获取元素 getValue 的实现
GET 方法实现
/**
* @author yby6
**/
public class MyHashMap<K, V> implements MyMap<K, V> {
/**
* 定义存储元素数组
*/
private Entry<K, V>[] table = null;
public MyHashMap() {
this.table = new Entry[16];
}
private int size = 0;
public int size() {
return size;
}
@Override
public V put(K k, V v) {
// 1.获取k的hashcode%16 = hash值 对应数组当中的位置
int hashValue = hash(k);
// 2.判断数组当中对应位置有没有元素
Entry<K, V> entry = table[hashValue];
if (null == entry) {
// 没有元素,直接存储 Entry<K,V>
table[hashValue] = new Entry<>(k, v, hashValue, null);
size++;
} else {
// 更新
if (table[hashValue].k.equals(k)) {
table[hashValue].v = v;
} else {
// 如果有元素,有hash碰撞,就要把数据使用头插法 插入到链表的头部,记录原来的值
table[hashValue] = new Entry<>(k, v, hashValue, entry);
size++;
}
}
return table[hashValue].getValue();
}
/**
* 哈希
*
* @param k k
* @return int
*/
private int hash(K k) {
int index = k.hashCode() % 16;
return index > 0 ? index : -index;
}
@Override
public V get(K k) {
// 1.判断当前集合中有没有元素,如果没有就直接返加null
if (size == 0) {
return null;
}
// 2.根据k获取的entry
Entry<K, V> entry = getEntry(k);
// 3.返回entry当中的value
return entry != null ? entry.getValue() : null;
}
private Entry<K, V> getEntry(K k) {
// 1.把k进行hash
int hashValue = hash(k);
for (Entry<K, V> e = table[hashValue]; e != null; e = e.next) {
if (hashValue == e.hash && e.getKey() == k || k.equals(e.getKey())) {
return e;
}
}
return null;
}
/**
* @author yby6
*/
class Entry<K, V> implements MyMap.Entry {
/**
* k
*/
K k;
/**
* v
*/
V v;
/**
* 哈希
*/
int hash;
/**
* 下一个节点元素
*/
Entry<K, V> next;
/**
* HashMap元素
*
* @param k k
* @param v v
* @param hash 哈希值
* @param next 下一个节点元素
*/
public Entry(K k, V v, int hash, Entry<K, V> next) {
this.k = k;
this.v = v;
this.hash = hash;
this.next = next;
}
@Override
public K getKey() {
return this.k;
}
@Override
public V getValue() {
return this.v;
}
}
}测试并使用
/**
* @author yby6
**/
public class HashTest {
public static void main(String[] args) {
MyMap<String, Object> personMap = new MyHashMap<>();
personMap.put("张三", "zs");
personMap.put("李四", "ls");
personMap.put("王五", "ww");
personMap.put("赵六", "zl");
personMap.put("周七", "zq");
personMap.put("郑八", "zb");
System.out.println(personMap.get("张三"));
}
}
img
最后
本期结束咱们下次再见👋~
🌊 关注我不迷路，如果本篇文章对你有所帮助，或者你有什么疑问，欢迎在评论区留言，我一般看到都会回复的。大家点赞支持一下哟~ 💗
我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
