数据结构哈希表(散列) 之Hash

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

声明: 此文章仅限于记录学习之用 , 受限于自身水平和理解能力 , 因此结论可能是不正确的. 如果您需要学习,建议参考其他文章

看了下网上一些大佬的教程, 写的云山雾绕的. 简单总结下吧. 以言简意赅为主.

介绍下hash

hash 就是把任意输入通过算法生成一个int值. 这个值就是放数据的地址, 然后在这个地址中存储数据.
注意: 不同的内容可能生成相同的哈希码, 这就是我们常说的hash冲突. 如何处理hash冲突问题,衍生了以下几套经典算法.
数据结构哈希表(散列) 之Hash,哈希算法,数据结构,散列表

使用演示hashMap 存取的过程.

根据key获取到 hashCode, 取到内存地址, 然后把value存入此区域.
数据结构哈希表(散列) 之Hash,哈希算法,数据结构,散列表
获取值也是同样道理.
数据结构哈希表(散列) 之Hash,哈希算法,数据结构,散列表
上图是最简易的hash存取示范. 结合刚刚说的"不同内容的hashCode可能相同", 因此是有hash冲突覆盖的情况.

解决hash冲突的常见方式

拉链寻址算法

从名字入手,可以更好的理解. 众所周知除了阿里巴巴喜欢胡乱造词, 大部分命名都有比较贴切的含义. 我看了下示例代码, 原来"拉链"不是衣服上的拉锁. 而是增加了y轴维度. 如果地址相同, 那就纵向排列. 拼多多这图最适合.

数据结构哈希表(散列) 之Hash,哈希算法,数据结构,散列表

示例代码
package hash_table;

import java.util.LinkedList;


/**
 * 拉链寻址的优点是可以有效地处理大量的哈希冲突,因为每个槽都可以包含一个链表,可以容纳更多的元素。
 * 然而,它也有一些缺点。
 * 例如,如果哈希表中有许多空槽,则可能会浪费大量内存,因为它需要为每个槽分配空间以存储链表头指针.
 * 此外,如果链表变得很长,则搜索元素所需的时间可能会增加。
 * @param <K>
 * @param <V>
 */
public class HashMapBySeparateChaining<K, V> {
    //定义一个存储链表的数组
    private final LinkedList<Node<K, V>>[] arr = new LinkedList[8];
    /**
     * 插入元素:首先计算元素的哈希值,并将其存储在哈希表中的相应槽中。然后,将元素添加到该槽中的链表中。
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        int index = key.hashCode() & (arr.length - 1);
        //如果此地址是空的, 直接创建一个链表, 将内容存进去
        if (arr[index] == null) {
            arr[index] = new LinkedList<>();
            arr[index].add(new Node<>(key, value));
        } else {
  			//如果此地址已经被占用了(hashCode冲突).就在链表中新增
            arr[index].add(new Node<>(key, value));
        }
    }

    /**
     * 查找元素:首先计算元素的哈希值,并找到其在哈希表中的相应槽。然后,在该槽的链表中搜索该元素。
     * @param key
     * @return
     */
    public V get(K key) {
        int idx = key.hashCode() & (arr.length - 1);
        for (Node<K, V> kvNode : arr[idx]) {
            if (key.equals(kvNode.getKey())) {
                return kvNode.value;
            }
        }
        return null;
    }

    /**
     * 定义实体类
     * @param <K>
     * @param <V>
     */
    static class Node<K, V> {
        final K key;
        V value;

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

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

    }

}


特点
  • 拉链寻址的优点是可以有效地处理大量的哈希冲突,因为每个槽都可以包含一个链表,可以容纳更多的元素。
  • 然而,它也有一些缺点。
  • 例如,如果哈希表中有许多空槽,则可能会浪费大量内存,因为它需要为每个槽分配空间以存储链表头指针.
  • 此外,如果链表变得很长,则搜索元素所需的时间可能会增加。

开放寻址算法

开放寻址算法,开放就是没有明确划分位置的,比如公共教室的座位, 地铁的座位,火车站大厅的座椅等…就是我们理解的随便坐. 比如你去上课, 你肯定有个最喜欢的位置,一般情况就坐那. 但是你的位置被占了, 作为新时代文明青年, 你不好去赶走人家, 只能从这个位置往后找,直到找到第一个空座就直接坐下了.
你可能问为啥是找到第一个空座就坐下, 这个这个生活场景中不好解释. 但是在哈希表中是为了节约空间,减少空槽
数据结构哈希表(散列) 之Hash,哈希算法,数据结构,散列表
请注意,需要把教室想象成一个哈希表(一维数组) .

示例代码
package hash_table;

import com.alibaba.fastjson.JSON;

/**
 * 开放寻址是一种解决哈希表中冲突的方法。
 * 当插入一个新的关键字时,如果发现该关键字对应的哈希地址已被其他关键字占用,
 * 则从当前哈希地址开始,按某种探查顺序连续探测可用的空地址,直至找到一个空地址为止。
 * @author Administrator
 * @param <K>
 * @param <V>
 */
public class HashMapByOpenAddressing<K, V> {


    private final Node<K, V>[] arr = new Node[8];

    public void put(K key, V value) {
        int index = key.hashCode() & (arr.length - 1);
        //如果此哈希地址为空,就直接存放
        if (arr[index] == null) {
            arr[index] = new Node<>(key, value);
        } else {
            //如果哈希地址被占用了, 就往后找空槽存进去
            for (int i = index; i < arr.length; i++) {
                if (arr[i] == null) {
                    arr[i] = new Node<>(key, value);
                    break;
                }
            }
        }
    }

    public V get(K key) {
        int idx = key.hashCode() & (arr.length - 1);
        //从hash地址开始往后找, 直到找到后返回
        for (int i = idx; i < arr.length; i++) {
            if (arr[i] != null && arr[i].key == key) {
                return arr[i].value;
            }
        }
        return null;
    }

    static class Node<K, V> {
        final K key;
        V value;

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

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

    }

    @Override
    public String toString() {
        return "HashMap{" +
                "arr=" + JSON.toJSONString(arr) +
                '}';
    }

}

特点

开放寻址的缺点很明显, 在get的时候, 如果产生hashCode冲突需要向后遍历获取, 效率太低了. 下面的合并散列来解决此问题.

合并散列

合并散列就是在开放寻址的基础上,进行了优化, 解决了查询时遍历数据效率过低的问题. 具体做法是,如果出现hashCode冲突, 向后找空槽存入, 原对象指向新对象. 表达不清晰,大家看下下图试试理解.

数据结构哈希表(散列) 之Hash,哈希算法,数据结构,散列表
数据结构哈希表(散列) 之Hash,哈希算法,数据结构,散列表

示例代码
package hash_table;

import com.alibaba.fastjson.JSON;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Objects;

/**
 * 合并散列(Coalesced hashing)是单独链接和开放寻址的混合,其中桶或节点在表中链接。该算法非常适合固定内存分配。通过识别哈希表上索引最大的空槽来解决合并哈希中的冲突,然后将冲突值插入该槽中。桶还链接到插入节点的插槽,其中包含其冲突哈希地址。
 */
public class HashMap04ByCoalescedHashing<K, V> implements Map<K, V> {

    private final Logger logger = LoggerFactory.getLogger(HashMap04ByCoalescedHashing.class);

    private final Node<K, V>[] tab = new Node[8];

    @Override
    public void put(K key, V value) {
        int idx = key.hashCode() & (tab.length - 1);
        //未冲突直接保存
        if (tab[idx] == null) {
            tab[idx] = new Node<>(key, value);
            return;
        }
        //key相同 value覆盖
        if (Objects.equals(tab[idx].key, key)) {
            tab[idx] = new Node<>(key, value);
            return;
        }
        //hash冲突时
        //找个下标
        int cursor = tab.length - 1;
        while (tab[cursor] != null && tab[cursor].key != key) {
            --cursor;
        }
        //把hash冲突的元素存起来
        tab[cursor] = new Node<>(key, value);

        // 将碰撞节点指向这个新节点
        while (tab[idx].idxOfNext != 0) {
            idx = tab[idx].idxOfNext;
        }

        tab[idx].idxOfNext = cursor;
    }

    @Override
    public V get(K key) {
        int idx = key.hashCode() & (tab.length - 1);
        while (tab[idx].key != key) {
            idx = tab[idx].idxOfNext;
        }
        return tab[idx].value;
    }

    static class Node<K, V> {
        final K key;
        V value;
        int idxOfNext;

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

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public int getIdxOfNext() {
            return idxOfNext;
        }

        public void setIdxOfNext(int idxOfNext) {
            this.idxOfNext = idxOfNext;
        }

    }

    @Override
    public String toString() {
        return "HashMap{" +
                "tab=" + JSON.toJSONString(tab) +
                '}';
    }

}

特点

请注意,合并散列寻址并不是常见的哈希表冲突解决策略。常用的冲突解决策略包括线性探测、二次探测和链地址法等。合并散列寻址更常用于特定场景下的优化。

布谷鸟散列算法

待更新

跳房子散列算法

待更新

罗宾汉哈希算法

待更新

参考资料

图片来源

  1. 拉链寻址原图来自拼多多商品.
  2. 开放寻址原图来自中国海洋大学官网
  3. 合并散列原图来自大河网新闻, 小傅哥 bugstack 虫洞栈

内容来源:
部分解释参考自: https://gitcode.com/search Ai搜索
目录结构及部分算法参考自小傅哥 bugstack 虫洞栈 (技术很好,但个人感觉他教程写的着实一般)文章来源地址https://www.toymoban.com/news/detail-832937.html

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

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

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

相关文章

  • 【数据结构】哈希表——闭散列 | 开散列(哈希桶)

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 哈希(Hash):是一种方法,将数据的key值和存储位置建立关系。 在之前学习过的顺序结构以及平衡树中,所有数据的key值和存储位置之间都没有对应的关系。所以在查找一个数据

    2023年04月24日
    浏览(45)
  • 数据结构算法设计——哈希表(散列表)

            哈希表 又叫 散列表 ,他们两个是同一个东西,本文全文采用“散列表”的叫法。散列表的本质其实就是一个 数组 ,他的作用就像使用数组时一样,输入下标可以得到对应元素,散列表可以实现 输入一个的时候得到这个的地址信息 。 下面是百科给出

    2024年02月03日
    浏览(60)
  • 【数据结构】哈希表的开散列和闭散列模拟

    在顺序和树状结构中,元素的存储与其存储位置之间是没有对应关系,因此在查找一个元素时,必须要经过多次的比较。 顺序查找的时间复杂度为0(N),树的查找时间复杂度为log(N)。 我们最希望的搜索方式:通过元素的特性,不需要对比查找,而是直接找到某个元素。 这一个

    2024年02月22日
    浏览(40)
  • C++王牌结构hash:哈希表开散列(哈希桶)的实现与应用

    目录 一、开散列的概念 1.1开散列与闭散列比较 二、开散列/哈希桶的实现 2.1开散列实现 哈希函数的模板构造 哈希表节点构造 开散列增容 插入数据 2.2代码实现 开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集

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

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

    2024年02月09日
    浏览(80)
  • 数据结构——散列函数、散列表

    散列表的基本概念 散列函数的构造方法 处理冲突的方法 散列查找及性能分析 提示:以下是本篇文章正文内容,下面案例可供参考 概念:之前的算法建立在“比较”基础上,效率取决于比较次数 散列函数:将映射成该对应地址的函数,记为Hash(key)=Addr,散列函

    2024年02月07日
    浏览(42)
  • 【数据结构】万字一文手把手解读哈希————(开/闭散列)解决哈希冲突完整详解(6)

    前言 大家好吖,欢迎来到 YY 滴 数据结构 系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁 主要内容含: 欢迎订阅 YY 滴C++专栏!更多干货持续更新!以下是传送门! YY的《C++》专栏 YY的《C++11》专栏 YY的《Linux》专栏 YY的《数据结构》专栏 YY的《C语言基础》专栏 YY的《

    2024年02月04日
    浏览(127)
  • 数据结构 in Golang:Hash Tables(哈希表)

    水果店的价格表: 苹果 Apple:3元 香蕉 Banana:4元 桃子 Peach:2元 梨 Pear:3元 找到一种水果的价格: 可以使用 binary search,通过名称来查找,耗时:O(logn) 如何只耗时 O(1) 来找到价格呢? Hash 函数:通过一个字符串 - 一个数值 例如: \\\"Apple\\\" - 1 \\\"Banana\\\" - 2 \\\"Peach\\\" - 7 \\\"Pear\\\" - 8 将字符

    2024年02月08日
    浏览(71)
  • 哈希表-散列表数据结构

    哈希表也叫散列表,哈希表是根据关键码值(key value)来直接访问的一种数据结构,也就是将关键码值(key value)通过一种映射关系映射到表中的一个位置来加快查找的速度,这种映射关系称之为哈希函数或者散列函数,存放记录的数组称之为哈希表。 哈希表采用的是一种转换思

    2024年01月21日
    浏览(55)
  • 【数据结构(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)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包