哈希表的实现（Java）

2402_86350741

498人浏览 · 2025-09-15 15:27:26

2402_86350741 · 2025-09-15 15:27:26 发布

引语

今天我打算实现一下哈希表的底层代码~~主要是实现两个版本的哈希表~~一个是较基础的版本~~这里面不包含引用类型~~第二个是包含引用类型的哈希表的实现~~让我们层层深入，步入编程的世界吧~~话不多说，让我们开始~~

首先~~我们都知道哈希表底层是用数组实现的~~，但是我们大家都知道哈希表是有哈希冲突的~~

如果我们像往常一样解决哈希表的冲突，使用线性探测法的话，并不能较好的解决哈希冲突~~

还有一种解决哈希冲突的方法~~（开散列法）是在一个数组上，如果有哈希冲突，会在数组上有冲突的位置上创建一个链表，使用链表来进行存储，这样就较好地解决哈希冲突~~这中并不像线性探测会占用数组中其他位置~~

今天哈希表表的实现就采用这种方法来进行实现~~

一.哈希表底层实现level1

哈希表的基本骨架

//  使用静态内部类~~ 作为链表的节点
    static class Node{
        public int key;
        public int value;
        public Node next;


//      给key value 进行初始化~~
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

//  创建一个数组
    public Node[] array;


//  统计哈希表的长度~~
    public int usedSize;

//  给数组进行初始化，所有元素为空
    public HashBlog() {
        array = new Node[10];
    }

put()的实现

    public void put(int key , int value){
//      通过哈希函数计算应该存放的数组下标
        int index = key % array.length;

        Node cur = array[index];
//      遍历链表
        while(cur != null){
//          更新其值
            if(cur.key == key){
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
//      如果没找到直接放入
        Node newNode = new Node(key, value);
//      使用链表的头插法
        newNode.next = array[index];
        array[index] = newNode;
        usedSize++;

//      判断负载因子是否过载~~
        if(loadFactor() >= 0.75){
            resize();
        }
    }

负载因子的计算

    public double loadFactor(){
        return usedSize*1.0 / array.length;
    }

哈希重组

    public void resize(){
        
//     新创建一个数组,进行扩容，为原数组的2倍
        Node[] newArray = new Node[array.length*2];

//      遍历原来的数组~~把原来数组的内容搬到新的数组


        for (int i = 0; i < array.length ; i++) {
            Node cur = array[i];
            while(cur != null){
//              记录下个节点的位置，避免这个节点进入新的数组后，节点丢失
                Node curNext = cur.next;
//              进算这个节点在新数组的位置~~
                int newIndex = cur.key % newArray.length;

//              进行头插
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = curNext;
            }
        }
//     数组是个引用类型，这个代码就是让array指向了newArray的数组~~
        array = newArray;
    }

get（）的实现

    public int get(int key){
 //     1.同意哈希函数计算应该存放的数组下标
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null){
            if(cur.key == key){
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;
    }

二.哈希表实现的level2

哈希表level2版本引入了泛型和对象哈希的概念，让我们哈希表从只能处理整数，升级到了可以处理任意乐平的键值对~~

引入Person类

class Person{
    public String id;

    public Person(String id) {
        this.id = id;
    }

    @Override
//  当两个对象的“ID号”一样，
    public boolean equals(Object o) {
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(id, person.id);
    }


//  这个方法是为每个引用类型产生了ID
    @Override
    public int hashCode() {
        return Objects.hashCode(id);
    }
}

哈希表基本骨架

//这里面引入了泛型~~
public class HashBuck2<K,V>{
    
    public K key;
    public V value;


//  静态内部类只能访问外部的静态成员变量~~
    static class Node<K,V>{
        public  K key;
        public V value;
        public Node<K,V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }


    public Node<K,V>[] array;

    public int usedSize;


//  给数组进行初始化
    public HashBuck2() {
        this.array =(Node<K,V>[]) new Node[10];
    }

put（）的实现

    public void put (K key, V value){
//      求引用类型的hashcode
        int hash = key.hashCode();
//      虽然hashCode的值很大，但是它是取余，所以它就是array.length长度里面的值~~~
        int index = hash % array.length;

        Node<K,V> cur= array[index];
//      遍历链表中是否有key 如果有key，将value值更新，并返回
//      若没有创建节点~~
        while(cur != null){
//          判断key是否相等
            if(cur.key.equals(key)){
                cur.value=value;
                return;
            }
            cur = cur.next;
        }

        Node<K,V> node = new Node<>(key,value);
//      使用头插法~~
        node.next = array[index];
        array[index] = node;
        usedSize++;

        //判断负载因子是否过载~~这个说明哈希太过拥挤~~
        if(loadFactor() >= 0.75){
            resize();
        }

    }

负载因子

//  计算负载因子
    public double loadFactor(){
        return usedSize*1.0 / array.length;
    }

resize()实现

    public void resize(){

//     新创建一个数组,进行扩容
        Node[] newArray = (Node<K,V>[]) new Node[array.length*2];

//      遍历原来的数组~~把原来数组的内容搬到新的数组


        for (int i = 0; i < array.length ; i++) {
            Node<K,V> cur = array[i];
            while(cur != null){

                Node<K,V> curNext = cur.next;
//              进算这个节点在新数组的位置~~
                int newIndex = cur.key .hashCode() % newArray.length;

//              进行头插
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = curNext;
            }
        }
//     数组是个引用类型，这个代码就是让array指向了newArray的数组~~
        array = newArray;
    }

get（）的实现

//  从key中获取key对应的值
    public V get (K key){
        int hash = key.hashCode();
//      从中获取下表
        int index = hash % array.length;

        Node<K,V> cur= array[index];
//     遍历链表
        while(cur != null){
            if(cur.key.equals(key)){
                return cur.value;
            }
            cur = cur.next;
        }
        return null;
    }

以上就是哈希表的基本实现~~