Java数据结构哈希算法之哈希桶方式解决哈希冲突
短信预约 -IT技能 免费直播动态提醒
一. 实现形式一（键值对只能为整数）
我们可以先实现一个比较简单的哈希表，使用java中解决哈希冲突的方法，即哈希桶（开散列）方式实现，其中注意：
- 可以使用内部类方式定义节点
- 负载因子默认为0.75
- 因为我们使用的是哈希桶方式解决哈希冲突，所以在我们扩容成功之后，原来桶中的数据得重新哈希计算出新的位置，不然就和原来桶中的数据的位置不一样了
相关代码如下
public class HashBucket {
static class Node {//使用内部类方式定义节点
public int key;
public int val;
public Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
private Node[] array;
public int usedSize;
public HashBucket() {
this.array = new Node[10];
this.usedSize = 0;
}
public void put(int key,int val) {//存放数据
//1、确定下标
int index = key % this.array.length;
//2、遍历这个下标的链表
Node cur = array[index];
while (cur != null) {
//更新val
if(cur.key == key) {
cur.val = val;
return;
}
cur = cur.next;
}
//3、cur == null 当前数组下标的链表中没有key
Node node = new Node(key,val);
node.next = array[index];
array[index] = node;
this.usedSize++;
//4、判断当前有没有超过负载因子
if(loadFactor() >= 0.75) {//负载因子我们认为0.75
//扩容
resize();
}
}
public int get(int key) {//取出数据
//以什么方式存储的 那就以什么方式取
int index = key % this.array.length;
Node cur = array[index];
while (cur != null) {
if(cur.key == key) {
return cur.val;
}
cur = cur.next;
}
return -1;
}
public double loadFactor() {//计算负载因子
return this.usedSize*1.0 / this.array.length;
}
public void resize() {//扩容函数
//自己创建新的2倍数组
Node[] newArray = new Node[2*this.array.length];
//遍历原来的哈希桶
//最外层循环 控制数组下标
for (int i = 0; i < this.array.length; i++) {
Node cur = array[i];
Node curNext = null;
while (cur != null) {
//记录cur.next
curNext = cur.next;
//在新的数组里面的下标
int index = cur.key % newArray.length;
//进行头插法
cur.next = newArray[index];
newArray[index] = cur;
cur = curNext;
}
}
this.array = newArray;
}
二. 实现方式二（改进版）
上面我们实现的哈希表中的键值对只能存放整型数据，但若是比较复杂的类型，例如字符串，对象等等，此时就需要用到泛型了。其中注意：
- 同样可以使用内部类方式定义节点类型
- 使用泛型
- 将泛型转换成整数时要用到
hashCode方法 - 利用对象哈希值确定下标，为了防止哈希值太大，应该让其%数组的长度
- 遍历数组下标时，利用equals方法比较key是否相同
- 存放自定义的数据类型时，一定要重写
hashcode和equals方法
相关代码如下
class Person {
public String id;
public Person(String id) {
this.id = id;
}
@Override
public String toString() {
return "Person{" +
"id='" + id + '\'' +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return Objects.equals(id, person.id);
}
@Override
public int hashCode() {
return Objects.hash(id);
}
}
public class HashBuck2<K,V> {
static class Node<K,V> {
public K key;
public V val;
public Node<K,V> next;
public Node(K key,V val) {
this.key = key;
this.val = val;
}
}
public Node<K,V>[] array = (Node<K, V>[]) new Node[10];
public int usedSize;
public void put(K key,V val) {
//通过hashcode方法定位数组的下标
int hash = key.hashCode();
int index = hash % this.array.length;
Node<K,V> cur = array[index];
while (cur != null) {
//equals 起的作用是遍历当前数组下标的key是否相同
if(cur.key.equals(key)) {
cur.val = val;
}
cur = cur.next;
}
Node<K,V> node = new Node<>(key,val);
node.next = array[index];
array[index] = node;
this.usedSize++;
}
public V get(K key) {
int hash = key.hashCode();
int index = hash % this.array.length;
Node<K,V> cur= array[index];
while (cur != null) {
if(cur.key.equals(key)) {
return cur.val;
}
cur = cur.next;
}
return null;
}
到此这篇关于Java 数据结构哈希算法之哈希桶方式解决哈希冲突的文章就介绍到这了,更多相关Java 哈希冲突内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
