当前位置：首页 > news >正文

哈希桶（详解创建）

news 来源：原创 2024/5/17 12:10:47

一、什么是哈希桶？

二、创建哈希桶

2.1创建节点以及哈希表。

2.2、添加节点

2.3、扩容（降低哈希冲突）

2.4、获取key

2.5、负载因子判断

一、什么是哈希桶？

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址（index = x % array.length()-1），具有相同地址的关键码归于同一子集合，每一个子集合称为一个哈希桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

如图，哈希是数组+链表结构，按照传入的元素放在通过散列函数计算出的散列地址处，如果再加入新的相同散列地址则向后通过链表将其链接在一起。

二、创建哈希桶

2.1创建节点以及哈希表。

key：关键码通过散列函数计算出的散列地址

val：节点对应的值

next：向后链接相同散列地址的节点地址

节点的创建：

static class Node {
    public int key;
    int val;
    Node next;
    public Node(int key,int val) {
        this.key =key;
        this.val = val;
    }
}
public Node[] array;

散列表的创建：

public Node[] array;
public int usedsize;

这里需要了解一个概念：

负载因子：x = 填入表中元素的个数 / 散列表的长度。

负载因子过高会提高哈希冲突率，所以我们想要增加元素并且降低冲突率就得增加散列表的长度

我们从源码中可以看到，DEFAULT_LOAD_FACTOR是源码默认的负载因子最大值为0.75f，所以我们在模拟创建中也以这个指标去扩展数组的长度。

2.2、添加节点

这里代码如下：grow代码在下一个

public void put(int key,int val) {
    int index = key%array.length-1;
    Node cur = array[index];
    while (cur!= null) {
        if (cur.key == key) {
            cur.val = val;
            return;
        }
    }
    Node node = new Node(key,val);
    node.next = array[index];
    array[index] = node;
    usedsize++;
    if (loadFactor() >= DEFAULT_LOAD_FACTOR) {
        grow();
    }
}

2.3、扩容（降低哈希冲突）

这里需要先提前标记下cur的下一个节点，不可以使用cur = cur.next ；因为遍历的cur.next会先把新位置链表的头节点接在cur的后面。

我们默认数组扩容为2倍扩容，并且遍历旧哈希表每一个节点放在新对应的散列地址处,因为数组扩容到了2倍会造成 index = x % array.length()-1 的散列地址改变。

private void grow() {
    Node[] newArray = new Node[array.length*2];
    for (int i = 0; i < array.length; i++) {
        Node cur =array[i];
        while (cur != null) {
            int index = cur.key% newArray.length-1;
            Node next = cur.next;
            cur.next = newArray[index];
            newArray[index] = cur;
            cur = cur.next;
        }
    }
    this.array = newArray;
}

2.4、获取key

通过遍历哈希表来找到对应的节点，如果不存在节点返回-1。

public int get(int key) {
    int index = key % array.length-1;
    Node cur = array[index];
    while (cur != null) {
        if (cur.key == key) {
            return cur.val;
        }
    }
    return -1;
}

2.5、负载因子判断

public float loadFactor() {
    return usedsize*1.0f / array.length;
}

完整代码放在Gitee：：HashBuck · 6442b0c · 404NOt/Repository-1 - Gitee.comhttps://gitee.com/N_404NOt/repository-1/commit/6442b0c94269d7f7b8406ce52bfe8e5ba5c175c9