Java实现哈希表的基本功能

2024-04-02 19:04:59 474人浏览泡泡鱼

Python 官方文档：入门教程 => 点击学习

摘要

目录一、哈希表头插法放入元素二、哈希表尾插法放入元素三、哈希表头插、尾插扩容四、找到key对应的value五、运行结果六、哈希表的泛型实现七、为什么jdk1.7及之前使用头插法而JD

一、哈希表头插法放入元素



public class HashBuck {

    class node {
        public int key;
        int value;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public int usedSize;
    public Node[] array;

    HashBuck() {
        this.array = new Node[8];
        this.usedSize = 0;
    }

    //JDk1.7及之前是头插法
    public void put1(int key, int value) {
        int index = key % this.array.length;
        Node node = new Node(key, value);
        Node cur = array[index];

        while (cur != null) {
            if (cur.key == key) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        node.next = array[index];
        array[index] = node;
        this.usedSize++;
        if (loadFactor() > 0.75) {
            resize1();
        }
    }
    public double loadFactor() {
        return this.usedSize / this.array.length * 1.0;
    }
}

二、哈希表尾插法放入元素


//JDK1.8是尾插法
    public Node findLast(Node head) {
        if (head == null) return head;
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        return cur;
    }
    public void put2(int key, int value) {
        int index = key % this.array.length;
        Node node = new Node(key, value);
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        Node last = findLast(array[index]);
        if (last == null) {
            array[index] = node;
            this.usedSize++;
            return;
        }
        last.next = node;
        this.usedSize++;
        if (loadFactor() > 0.75) {
            resize2();
        }
    }

三、哈希表头插、尾插扩容


public void resize1() {
        Node[] newArray = new Node[this.array.length * 2];
        for (int i = 0; i < this.array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                int index = cur.key % newArray.length;
                Node curNext = cur.next;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }
        this.array = newArray;
    }
    //resize尾插
    public void resize2() {
        Node[] newArray = new Node[this.array.length * 2];
        for (int i = 0; i < this.array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                int index = cur.key % newArray.length;
                Node curNext = cur.next;
                Node last = findLast(newArray[index]);
                if (last == null) {
                    newArray[index] = cur;
                    break;
                }
                last.next = cur;
                cur = curNext;
            }
        }
        this.array = newArray;
    }

    public Node findLast(Node head) {
        if (head == null) return head;
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        return cur;
    }

四、找到key对应的value


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

五、运行结果


class HashBuckTest {
    public static void main(String[] args) {
        HashBuck hashBuck = new HashBuck();
       //头插
        hashBuck.put1(9,451);
        hashBuck.put1(17,455);
       //尾插
       //hashBuck.put2(9,451);
       //hashBuck.put2(17,455);
        hashBuck.put1(2,45);
        hashBuck.put1(3,14);
        hashBuck.put1(4,52);
        hashBuck.put1(4,89);
        System.out.println(hashBuck.get(1));
        System.out.println("+=================");
    }
}

头插

在这里插入图片描述

尾插

在这里插入图片描述

扩容


class HashBuckTest {
    public static void main(String[] args) {
        HashBuck hashBuck = new HashBuck();
//        hashBuck.put1(9, 451);
//        hashBuck.put1(17, 455);
        hashBuck.put1(1, 589);
        hashBuck.put1(2, 45);
        hashBuck.put1(3, 14);
        hashBuck.put1(4, 52);
        hashBuck.put1(4, 1);
        hashBuck.put1(6, 829);
        hashBuck.put1(7, 72);
        hashBuck.put1(8, 8279);
        hashBuck.put2(9,451);
        hashBuck.put2(15,455);
        hashBuck.put2(31,451);
        System.out.println(hashBuck.get(7));
        System.out.println(hashBuck.get(4));
        System.out.println(hashBuck.get(15));
        System.out.println(hashBuck.get(31));
    }
}

在这里插入图片描述

get

在这里插入图片描述

六、哈希表的泛型实现


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;
    public int usedSize;

    public HashBuck2() {
        this.array = (Node<K, V>[]) new Node[8];
    }

    public void put(K key, V val) {
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K, V> cur = array[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        Node<K, V> node = new Node<>(key, val);
        node.next = array[index];
        array[index] = node;
        this.usedSize++;
        if (loadFactor() > 0.75) {
            resize();
        }
    }

    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.val;
            }
            cur = cur.next;
        }
        return null;
    }
    public void resize() {
        Node[] newArray = new Node[this.array.length * 2];
        for (int i = 0; i < this.array.length; i++) {
            Node<K,V> cur = array[i];
            while (cur != null) {
                int hash = cur.key.hashCode();
                int index = hash % array.length;
                Node <K,V>curNext = cur.next;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }
        this.array = newArray;
    }
    public double loadFactor() {
        return this.usedSize / this.array.length * 1.0;
    }
}



class Student{
    public int id;
    Student(int id){
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return id == student.id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}
class HashBuck2Test{
    public static void main(String[] args) {
        HashBuck2<Student,Integer> hashBuck2 = new HashBuck2<>();
        Student s1 = new Student(10001);
        Student s2 = new Student(10001);
        Student s3 = new Student(10003);
        hashBuck2.put(s1,89);
        hashBuck2.put(s1,60);
        hashBuck2.put(s2,94);
        hashBuck2.put(s3,100);
        System.out.println(hashBuck2.get(s1));
        System.out.println(hashBuck2.get(s2));
    }
}

注意：

要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode 一定是一致的。
比如Student s1 和 s2 的id一样，得到的却是不同的value，所以要覆写hashCode 和 equals 方法，如果不覆写，则使用的是Object类的hashCode 和 equals 方法，比较的是地址。

在这里插入图片描述

重写之后

在这里插入图片描述

七、为什么JDK1.7及之前使用头插法而JDK1.8使用尾插法

hashmap用数组+链表。数组是固定长度，链表太长就需要扩充数组长度进行rehash减少链表长度。如果两个线程同时触发扩容，在移动节点时会导致一个链表中的2个节点相互引用，从而生成环链表

到此这篇关于Java实现哈希表的基本功能的文章就介绍到这了,更多相关哈希表基本功能实现内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

您可能感兴趣的文档:

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: Java实现哈希表的基本功能

本文链接: https://www.lsjlt.com/news/126590.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

Java实现哈希表的基本功能

目录一、哈希表头插法放入元素二、哈希表尾插法放入元素三、哈希表头插、尾插扩容四、找到key对应的value五、运行结果六、哈希表的泛型实现七、为什么JDK1.7及之前使用头插法而JD...

99+

2024-04-02
怎么在Java中实现哈希表

本篇文章为大家展示了怎么在Java中实现哈希表，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。一、哈希表头插法放入元素public class HashBuck {&nb...

99+

2023-06-15
Java哈希表和有序表如何实现

这篇文章主要介绍“Java哈希表和有序表如何实现”，在日常操作中，相信很多人在Java哈希表和有序表如何实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Java哈希表和有序表如何实现”的疑惑有所帮助！接下来...

99+

2023-07-06
Java哈希表和有序表怎么实现

本文小编为大家详细介绍“Java哈希表和有序表怎么实现”，内容详细，步骤清晰，细节处理妥当，希望这篇“Java哈希表和有序表怎么实现”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。哈希表（HashMap）hash查...

99+

2023-07-06
C++ 哈希表的基本用法及说明

目录C++ 哈希表基本用法为什么要用哈希表遍历查找插入删除C++ 哈希表基础知识常见的三种哈希结构C++ 哈希表基本用法哈希表是一种很常见的数据结构，我现在平时刷算法题一...

99+

2024-04-02
JavaScript如何实现哈希表

这篇文章将为大家详细讲解有关JavaScript如何实现哈希表，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。一、哈希表原理哈希表是一种非常重要的数据结构，几乎所有的编程语言都有直接或者间接的应用这种数据结...

99+

2023-06-22
JavaScript实现哈希表的方法

本篇内容主要讲解“JavaScript实现哈希表的方法”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“JavaScript实现哈希表的方法”吧!哈希表通常是基于数...

99+

2024-04-02
详解JavaScript实现哈希表

目录一、哈希表原理二、哈希表的概念三、哈希化冲突问题1、链地址法2、开放地址法四、哈希函数的实现五、封装哈希表六、哈希表操作1、插入&修改操作2、获取操作3、删除操作4、判断...

99+

2024-04-02
C++实现哈希散列表的示例

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这...

99+

2024-04-02
哈希表的原理及实现代码

哈希表可以表述为，是一种可以根据关键字快速查询数据的数据结构一. 哈希表有哪些优点？不论哈希表中数据有多少，增加，删除，改写数据的复杂度平均都是O(1)，效率非常高二. 实现哈希表 1. 哈希表原理如果说每一个数据它都对应着一个固...

99+

2023-01-31

原理代码哈希表
C++数据结构之哈希表的实现

目录哈希表概念散列函数直接定址法除留余数法平方取中法哈希冲突线性探测二次探测链地址法哈希表的实现闭散列开散列哈希表概念二叉搜索树具有对数时间的表现，但这样的表现建立在一个假设上：输...

99+

2023-03-11

C++数据结构哈希表 C++哈希表 C++数据结构
Java中哈希表的示例分析

这篇文章将为大家详细讲解有关Java中哈希表的示例分析，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。1，概念顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过...

99+

2023-06-29
java哈希表的原理是什么

Java哈希表的原理是利用哈希函数将键(key)映射到存储位置，通过对键进行哈希运算得到一个索引，然后将值(value)存储在该索引...

99+

2023-08-24

java
Java真题实练掌握哈希表的使用

目录1.多数元素题目描述思路详解代码与结果2.数组中的k-diff数对题目描述思路详解代码与结果3.缺失的第一个正数题目描述思路详解代码与结果1.多数元素题目描述思路详解这个...

99+

2024-04-02
Java哈希表和有序表实例代码讲解

目录哈希表（HashMap）按值传递按址传递内存大小比较有序表（TreeMap）哈希表（HashMap） hash查询的时间复杂度是O(1) 按值传递 Character，Short...

99+

2023-05-15

Java哈希表和有序表 Java哈希表 Java有序表
Java数据结构之实现哈希表的分离链接法

哈希表的分离链接法原理 Hash Table可以看作是一种特殊的数组。他的原理基本上跟数组相同，给他一个数据，经过自己设置的哈希函数变换得到一个位置，并在这个位置当中放置该数据。哦...

99+

2024-04-02
Java数据结构中实现哈希表的分离链接法

这篇文章主要介绍“Java数据结构中实现哈希表的分离链接法”，在日常操作中，相信很多人在Java数据结构中实现哈希表的分离链接法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Java数据结构中实现哈希表的分离...

99+

2023-06-20
Javascript中怎么实现一个伪哈希表

这期内容当中小编将会给大家带来有关Javascript中怎么实现一个伪哈希表，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。javascript中实现哈希表的代码：1 fu...

99+

2024-04-02
Golang哈希算法实现配置文件的监控功能详解

目录Golang hash256实现包使用sha256.New()使用sha256.Sum256()函数监控配置文件变化获取配置hash值总结SHA(secure hashing a...

99+

2023-03-08

Go哈希算法监控配置文件 Go哈希算法
PHP 哈希表的原理、实现与常见问题

哈希表通过哈希函数将键映射到数组下标，实现快速查找、插入和删除。php 使用数组和 md5() 哈希函数实现哈希表，通过线性探查解决冲突。常见问题包括哈希冲突（可通过增加数组大小或优化哈...

99+

2024-05-07

php 哈希表