Java实现数据结构哈希表

这篇具有很好参考价值的文章主要介绍了Java实现数据结构哈希表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

哈希表

概述

给美分数据分配一个编号,放入表格(数组)

建立编号与表格索引的关系,将来就可以通过编号快速查找数据

  1. 理想情况编号当唯一,数组能容纳所有数据
  2. 现实是不能说为了容纳所有数据造一个超大数组,编号也可能重复

解决

  1. 有限长度的数组,以[拉链]方式存储数据
  2. 允许编号适当重复,通过数据自身来进行区分

代码

基础代码

public class HahTable {
    //节点类
    static class Entry{
        int hash;   //哈希码
        Object key; //键
        Object value;   //值
        Entry next;

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }
    //创建一个数组,数组里面装的是Entry节点,也就是链表的头节点
    Entry[] table = new Entry[16];
    int size = 0;   //元素个数
}

获取

Java实现数据结构哈希表,数据结构,散列表

这里实际上可以使用取余运算,如果key值是9,8对数组的长度进行求余数,可以得出来是0,所以可以在数组0的那根链表上继续进行查找

可以看出索引3位置处就没有元素,返回的就是null

//根据hash码获取value
    private Object get(int hash,Object key){
        //hash码与数组的长度减一,实际上取到的就是索引值
        int index = hash & (table.length - 1);
        //如果数组的该索引位置处没有值的话,也不会有对应的value值,所以可以直接返回
        if(table[index] == null){
            return null;
        }
        //将table数组处index索引位置处的链表找到
        Entry p = table[index];
        //遍历链表
        while (p != null){
            //如果链表的key和传过来的key值相等的话可以直接将key值当值节点返回
            if(p.key.equals(key)){
                return p;
            }
            p = p.next;
        }
        //找到最后都没有的话,返回null值
        return null;
    }

插入

Java实现数据结构哈希表,数据结构,散列表

插入实际上也是,索引3位置处并没有内容,所以可以直接插入,而其他索引位置处就需要找到链表进行对应的位置插入了

 //向hash表存入新的key,value,如果key重复,则更新value
    private void put(int hash,Object key,Object value){
        //hash码与数组的长度减一,实际上取到的就是索引值
        int index = hash & (table.length - 1);
        //接下来会有两种情况
        //第一种:index索引位置处有空位置,直接新增
        if(table[index] == null){
           table[index] = new Entry(hash,key,value);
        }else{
            //第二种:index索引位置处没有空位,沿着链表查找,有key值的话,更新,没有的话新增
            Entry p = table[index];
            //遍历链表
            while (true){
                //如果链表的key和传过来的key值相等的话可以直接将key值当值节点返回
                if(p.key.equals(key)){
                    p.value = value;
                    return;
                }
                if(p.next == null){
                    break;
                }
                p = p.next;
            }
            //此时的p就是最后一个节点
            p.next = new Entry(hash,key,value);
        }
        size++;
    }

删除

//根据hash码删除,返回删除的value
    private Object remove(int hash,Object key){
        //hash码与数组的长度减一,实际上取到的就是索引值
        int index = hash & (table.length - 1);
        //如果数组的index位置处为null,直接返回null
        if(table[index] == null){
            return null;
        }
        //找到数组索引位置处的链表
        Entry p = table[index];
        Entry prev = null;//设置删除节点的父节点
        while (p != null){
            if(p.key.equals(key)){
                //找到了删除节点
                //如果删除的是头节点的话,将数组索引位置处的元素设置为链表头节点的下一个元素
                if(prev == null){
                    table[index] = p.next;
                }else{
                    //如果不是的话,将父节点的next指向儿子节点的next,这样就把儿子节点忽略掉了
                    prev.next = p.next;
                }
                return p.value;
            }
            prev = p;   //将当前节点设置称为删除节点的父节点
            p = p.next;
        }
        return null;
    }

此时会出现一个问题,就是如果说元素内容并不多,但是数组长度会很长则造成了空间的浪费,如果说数组长度不长,但是元素足够多就会导致增删改查的效率变低,所以需要在合适的时候对数组进行扩容,这里就引出了一个新的名词负载因子

扩容

负载因子公式如下图所示

Java实现数据结构哈希表,数据结构,散列表

  • 从上面可以看出n代表的是元素的个数,m代表的是数组的长度,他们的比值最好在4分之3左右
  • 扩容之后一般采取的办法是容量进行翻倍

Java实现数据结构哈希表,数据结构,散列表

 float loadFactor = 0.75f;//负载因子大小  12称为阈值
    int threshold =(int) (loadFactor * table.length);//这个实际上计算的实际上就是阈值

//向hash表存入新的key,value,如果key重复,则更新value
    private void put(int hash,Object key,Object value){
        //hash码与数组的长度减一,实际上取到的就是索引值
        int index = hash & (table.length - 1);
        //接下来会有两种情况
        //第一种:index索引位置处有空位置,直接新增
        if(table[index] == null){
           table[index] = new Entry(hash,key,value);
        }else{
            //第二种:index索引位置处没有空位,沿着链表查找,有key值的话,更新,没有的话新增
            Entry p = table[index];
            //遍历链表
            while (true){
                //如果链表的key和传过来的key值相等的话可以直接将key值当值节点返回
                if(p.key.equals(key)){
                    p.value = value;
                    return;
                }
                if(p.next == null){
                    break;
                }
                p = p.next;
            }
            //此时的p就是最后一个节点
            p.next = new Entry(hash,key,value);
        }
        size++;
        if(size > threshold){
            resize();
        }
    }

    /**
     * 扩容方法
     */
    private void resize() {
        Entry[] newTable = new Entry[table.length << 1];    //移位比直接乘以2效率更高
        for (int i = 0; i < table.length; i++) {
            Entry p = table[i];
            if(p != null){
                //拆分链表,移动到新的数组

                /*
                   拆分规律
                   * 一个链表最多拆成两个
                   * hash & table.length == 0 的一组
                   * hash & table.length != 1 的一组
                 */
            }
        }
        table = newTable;//扩容完成之后将新数组赋值给旧数组
        threshold = threshold =(int) (loadFactor * table.length);
    }

讲到这里就需要科普一个知识了
0 (二进制: 0000) & (按位与) 8 (二进制: 1000)   结果0

8 (二进制: 1000) & (按位与) 8 (二进制: 1000)    结果8

16 (二进制: 10000) & (按位与) 8 (二进制: 1000)  结果0

24 (二进制: 11000) & (按位与) 8 (二进制: 01000)  结果8

可以看出如果最后四位的值相等的时候结果为8,否则结果为0

Java实现数据结构哈希表,数据结构,散列表

 /**
     * 扩容方法
     */
    private void resize() {
        // 创建新的Entry数组,长度为原数组的两倍(通过位运算效率更高)
        Entry[] newTable = new Entry[table.length << 1];

        // 遍历原数组
        for (int i = 0; i < table.length; i++) {
            Entry p = table[i];

            // 如果当前位置有链表
            if(p != null){
                // 拆分链表,移动到新的数组
            /*
               拆分规律
               * 一个链表最多拆成两个
               * hash & table.length == 0 的一组
               * hash & table.length != 1 的一组
             */

                // 创建两个新的链表,一个是a,另一个是b
                Entry a = null;
                Entry b = null;
                Entry aHead = null;
                Entry bHead = null;

                // 递归遍历链表
                while (p != null){
                    // 如果当前节点的hash与数组的长度 == 0的时候添加到a,否则添加到b
                    if((p.hash & table.length) == 0){
                        if(a != null){
                            a.next = p;
                        }else{
                            aHead = p;
                        }
                        // 分配到a
                        a = p;
                    }else{
                        if(b != null){
                            b.next = p;
                        }else{
                            bHead = p;
                        }
                        // 分配到b
                        b = p;
                    }
                    // 进行递归遍历
                    p = p.next;
                }

                // 将链表a添加到新数组的原位置
                if(a != null ){
                    a.next = null;
                    newTable[i] = aHead;
                }

                // 将链表b添加到新数组的原位置的后半部分
                if(b != null ){
                    b.next = null;
                    newTable[i + table.length] = bHead;
                }
            }
        }

        // 扩容完成之后将新数组赋值给旧数组
        table = newTable;

        // 更新阈值
        threshold = (int) (loadFactor * table.length);
    }

哈希算法

概述

hash算法是将任意对象,分配一个编号的过程,其中编号是一个有限范围内的数字(如int范围内),hash算法是一种将任意长度的数据通过一个算法,变成固定长度数据的过程,这个固定长度的数据就是hash值。hash算法可以将任意大小的数据压缩到固定大小的值。常见的hash算法有MD5、SHA1、SHA256、SHA512、CRC32等。其中,MD5和SHA系列算法是最常用的hash算法。这些算法在计算hash值时,都考虑了原始数据的每一个字节,一旦改动原始数据的任何一个字节,所得到的hash值都会有明显的不同。因此,hash算法被广泛应用于数据完整性校验和加密等方面。

Java实现数据结构哈希表,数据结构,散列表

在java里面可以调用对象的HashCode方法来进行获取文章来源地址https://www.toymoban.com/news/detail-833514.html

字符串生成hash的方法

public static void main(String[] args) {
        String str = "abc";
        System.out.println(str.hashCode());

        System.out.println("==================");
        int hash = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            hash = hash * 31 +c;
        }
        System.out.println(hash);

    }

到了这里,关于Java实现数据结构哈希表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构(C++版)】哈希表(散列表)

    目录   1. 散列表的概念 2. 散列函数的构造方法 2.1 直接定址法 2.2 除留余数法 2.3 数字分析法 2.4 平方取中法 3. 处理冲突的方法 3.1 开放定址法 3.1.1 线性探测法 3.1.2 平方探测法 3.1.3 双散列法 3.1.4 伪随机序列法 3.2 拉链法(链接法) 4. 散列查找及性能分析 5. 哈希的应用 5.1 位

    2024年02月15日
    浏览(45)
  • 【数据结构与算法】04 哈希表 / 散列表 (哈希函数、哈希冲突、链地址法、开放地址法、SHA256)

    一种很好用,很高效,又一学就会的数据结构,你确定不看看? 莫慌,每个概念都很好理解。 哈希表( Hash Table ),也称为 散列表 ,是一种数据结构, 用于存储键值对(key-value pairs) 。 键值对是一种数据结构,用于将键(key)与对应的值(value)相关联。在键值对中,键

    2024年02月09日
    浏览(78)
  • 一篇就能学懂的散列表,让哈希表数据结构大放光彩

    目录 1.散列表的基本概念 2.散列表的查找 3.散列函数的构造方法 1.直接定址法 2.除留余数法 4.散列表解决冲突的方法 1.开放定址法 2.链地址法 基本思想 :记录的存储位置与之间存在的对应关系 对应关系——hash函数 Loc(i) = H(keyi) Hash:哈希——翻译为:散列、杂凑(感

    2024年02月09日
    浏览(52)
  • 【JavaSE专栏55】Java集合类HashTable解析,基于哈希表实现的唯一性键值对存储数据结构

    作者主页 :Designer 小郑 作者简介 :3年JAVA全栈开发经验,专注JAVA技术、系统定制、远程指导,致力于企业数字化转型,CSDN学院、蓝桥云课认证讲师。 主打方向 :Vue、SpringBoot、微信小程序 本文讲解了 Java 中集合类 HashTable 的语法、使用说明和应用场景,并给出了样例代码。

    2024年02月15日
    浏览(54)
  • 数据结构-哈希-哈希表实现

    🚀理想的搜索方法:不经过任何的比较,一次直接从表中得到要搜索的元素。如果构造一种存储结构,通过某种函数使元素的存储位置与其关键码之间能够建立起一一映射的关系,那么在查找的时候就能通过此函数快速的找到该元素。 🚀向该结构中插入元素:根据该元素的

    2024年02月10日
    浏览(36)
  • 「数据结构」哈希表2:实现哈希表

    🎇 个人主页 :Ice_Sugar_7 🎇 所属专栏 :Java数据结构 🎇 欢迎点赞收藏加关注哦! 在讲插入之前需要先了解扩容,因为 插入后载荷因子如果超过阈值,那我们就要扩容,即扩容是插入操作的一部分 扩容后,原先哈希表中的元素的哈希地址会改变。之前会发生哈希冲突的元素

    2024年02月21日
    浏览(39)
  • 【数据结构】 | java中 哈希表及其冲突解决

    🎗️ 博客新人,希望大家一起加油进步 🎗️ 乾坤未定,你我皆黑马 1、哈希表概念 顺序结构以及平衡树中 ,元素关键码与其存储位置之间没有对应的关系,因此在 查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(Lo

    2024年01月19日
    浏览(46)
  • 【Java数据结构】顺序表、队列、栈、链表、哈希表

    是一个有类型参数(type parameter)的范型表(generic class) 能够自动调整容量,并且不需要写额外的代码 存放数据使用数组但是可以编写一些额外的操作来强化为线性表,底层依然采用顺序存储实现的线性表,称为顺序表 创建 常见操作 一旦确认数组列表大小恒定,不再发生

    2024年02月02日
    浏览(41)
  • 【数据结构篇C++实现】- 哈希表

    友情链接:C/C++系列系统学习目录 哈希表:也叫做散列表。是根据和值(Key-Value)直接进行访问的数据结构。也就是说,它通过 key 和一个映射函数 Hash(key) 计算出对应的一个存储位置,然后把键值对映射到哈希表上的对应位置来访问记录,以加快查找的速度。这

    2024年02月02日
    浏览(43)
  • java数据结构(哈希表—HashMap)含LeetCode例题讲解

      目录 1、HashMap的基本方法 1.1、基础方法(增删改查) 1.2、其他方法  2、HashMap的相关例题 2.1、题目介绍 2.2、解题 2.2.1、解题思路 2.2.2、解题图解 2.3、解题代码 HashMap 是一个散列表,它存储的内容是键值(key-value)映射。 HashMap 的 key 与 value 类型可以相同也可以不同,根据定

    2024年02月05日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包