Python 官方文档:入门教程 => 点击学习
一. 实现形式一(键值对只能为整数) 我们可以先实现一个比较简单的哈希表,使用java中解决哈希冲突的方法,即哈希桶(开散列)方式实现,其中注意: 可以使用内部类方式定义节
我们可以先实现一个比较简单的哈希表,使用java中解决哈希冲突的方法,即哈希桶(开散列)方式实现,其中注意:
相关代码如下
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
方法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 哈希冲突内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: Java数据结构哈希算法之哈希桶方式解决哈希冲突
本文链接: https://www.lsjlt.com/news/138959.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0