Java 数据结构哈希算法之哈希桶方式解决哈希冲突

Java 数据结构哈希算法之哈希桶方式解决哈希冲突

一. 实现形式一（键值对只能为整数）

我们可以先实现一个比较简单的哈希表，使用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 {

static class Node {

public K key;

public V val;

public Node next;

public Node(K key,V val) {

this.key = key;

this.val = val;

}

}

public Node[] array = (Node[]) new Node[10];

public int usedSize;

public void put(K key,V val) {

//通过hashcode方法定位数组的下标

int hasgGTYAh = key.hashCode();

int index = hash % this.array.length;

Node cur = array[index];

while (cur != null) {

//equals 起的作用是遍历当前数组下标的key是否相同

if(cur.key.equals(key)) {

cur.val = val;

}

cur = cur.next;

}

Node 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 cur= array[index];

while (cur != null) {

http:// if(cur.key.equals(key)) {

regGTYAturn cur.val;

}

cur = cur.next;

}

return null;

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。