处理哈希冲突的常见方法（五种）

1、开放地址法（Open Addressing）：

  • 线性探测（Linear Probing）： 当发生冲突时，顺序地查找下一个可用的槽位，直到找到空槽或者整个表被搜索一遍。这个方法的缺点是可能出现“聚簇”（cluster）现象，即连续的槽位被占用，影响性能。在线性探测中，当发生冲突时，会顺序地查找下一个可用的槽位，直到找到空槽或者整个表被搜索一遍。
class LinearProbingHashTable {
    private int[] table;
    private int size;

    public LinearProbingHashTable(int capacity) {
        table = new int[capacity];
        size = 0;
    }

    public void insert(int key) {
        int index = hash(key);
        while (table[index] != 0) {
            index = (index + 1) % table.length;
        }
        table[index] = key;
        size++;
    }

    // Other methods: search, delete, resize, etc.
}
  • 二次探测（Quadratic Probing）： 类似于线性探测，但探测的步长变成了一个二次方程，以减缓聚簇的形成。二次探测类似于线性探测，但是探测的步长变成了一个二次方程，以减缓聚簇的形成。
class QuadraticProbingHashTable {
    private int[] table;
    private int size;

    public QuadraticProbingHashTable(int capacity) {
        table = new int[capacity];
        size = 0;
    }

    public void insert(int key) {
        int index = hash(key);
        int i = 1;
        while (table[index] != 0) {
            index = (index + i * i) % table.length;
            i++;
        }
        table[index] = key;
        size++;
    }

    // Other methods: search, delete, resize, etc.
}
  • 双重散列（Double Hashing）： 使用第二个哈希函数来计算探测步长，从而避免线性探测和二次探测中可能出现的聚簇问题。使用第二个哈希函数来计算探测步长，从而避免线性探测和二次探测中可能出现的聚簇问题。
class DoubleHashingHashTable {
    private int[] table;
    private int size;

    public DoubleHashingHashTable(int capacity) {
        table = new int[capacity];
        size = 0;
    }

    public void insert(int key) {
        int index = hash(key);
        int stepSize = hash2(key);
        while (table[index] != 0) {
            index = (index + stepSize) % table.length;
        }
        table[index] = key;
        size++;
    }

    private int hash2(int key) {
        // Choose a second hash function
        return 5 - (key % 5); // Example second hash function
    }

    // Other methods: search, delete, resize, etc.
}

2、链地址法（Chaining）：

  • 每个哈希桶存储一个链表（或其他数据结构，如红黑树）。当发生冲突时，新的元素被插入到相应的链表中。这样，相同哈希值的元素被存储在同一个哈希桶中，而不会影响其他哈希桶。链地址法的缺点是在处理大量冲突时可能会引入额外的空间和指针开销。
a. 建立链表（Chaining）：

每个哈希桶存储一个链表，当发生冲突时，新的元素被插入到相应的链表中。

import java.util.LinkedList;

class ChainingHashTable {
    private LinkedList<Integer>[] table;
    private int size;

    public ChainingHashTable(int capacity) {
        table = new LinkedList[capacity];
        size = 0;
        for (int i = 0; i < capacity; i++) {
            table[i] = new LinkedList<>();
        }
    }

    public void insert(int key) {
        int index = hash(key);
        table[index].add(key);
        size++;
    }

    // Other methods: search, delete, resize, etc.
}
b. Coalesced Hashing：

Coalesced Hashing是一种混合了开放地址法和链地址法思想的方法，所有元素都存储在一个大数组中。

class CoalescedHashTable {
    private int[] table;
    private int[] next;
    private int size;

    public CoalescedHashTable(int capacity) {
        table = new int[capacity];
        next = new int[capacity];
        size = 0;
        for (int i = 0; i < capacity; i++) {
            next[i] = -1; // Initialize all next pointers to -1
        }
    }

    public void insert(int key) {
        int index = hash(key);
        if (table[index] == 0) {
            table[index] = key;
        } else {
            int currentIndex = index;
            while (next[currentIndex] != -1) {
                currentIndex = next[currentIndex];
            }
            next[currentIndex] = size;
            table[size] = key;
        }
        size++;
    }

    // Other methods: search, delete, resize, etc.
}

3、再哈希（Rehashing）：

  • 当哈希表的负载因子达到一定阈值时，进行再哈希操作，即重新调整哈希表的大小。这通常涉及创建一个更大的哈希表，然后将所有已有元素重新插入。这样可以减少冲突的可能性，但是会引起一定的性能开销。

import java.util.Arrays;

class RehashingHashTable {
    private int[] table;
    private int size;
    private static final double LOAD_FACTOR_THRESHOLD = 0.7;

    public RehashingHashTable(int initialCapacity) {
        table = new int[initialCapacity];
        size = 0;
    }

    public void insert(int key) {
        if ((double) size / table.length > LOAD_FACTOR_THRESHOLD) {
            rehash();
        }
        int index = hash(key);
        while (table[index] != 0) {
            index = (index + 1) % table.length;
        }
        table[index] = key;
        size++;
    }

    private void rehash() {
        int newCapacity = table.length * 2; // Double the capacity
        int[] newTable = new int[newCapacity];
        Arrays.fill(newTable, 0);

        for (int key : table) {
            if (key != 0) {
                int newIndex = key % newCapacity;
                while (newTable[newIndex] != 0) {
                    newIndex = (newIndex + 1) % newCapacity;
                }
                newTable[newIndex] = key;
            }
        }

        table = newTable;
    }

    // Other methods: search, delete, etc.
}

4、建立公共溢出区域（Overflow Area）：

  • 将所有冲突的元素都放入一个公共溢出区域。这个区域通常是一个链表或其他数据结构，而哈希表的槽位只存储指向这个区域的指针。这样可以避免在哈希表主体中进行过多的线性探测，但仍需要额外的空间。

import java.util.LinkedList;

class OverflowAreaHashTable {
    private LinkedList<Integer>[] table;
    private LinkedList<Integer> overflowArea;
    private int size;

    public OverflowAreaHashTable(int capacity) {
        table = new LinkedList[capacity];
        overflowArea = new LinkedList<>();
        size = 0;
        for (int i = 0; i < capacity; i++) {
            table[i] = new LinkedList<>();
        }
    }

    public void insert(int key) {
        int index = hash(key);
        if (!table[index].isEmpty()) {
            overflowArea.add(key);
        } else {
            table[index].add(key);
        }
        size++;
    }

    // Other methods: search, delete, etc.
}

5、Coalesced Hashing：

  • 这是一种混合了开放地址法和链地址法思想的方法。在Coalesced Hashing中，所有元素都存储在一个大数组中，而不是在链表中。冲突时，使用某种策略将元素插入到数组中的其他位置，以避免聚簇。

class CoalescedHashTable {
    private int[] table;
    private int[] next;
    private int size;

    public CoalescedHashTable(int capacity) {
        table = new int[capacity];
        next = new int[capacity];
        size = 0;
        Arrays.fill(next, -1); // Initialize all next pointers to -1
    }

    public void insert(int key) {
        int index = hash(key);
        if (table[index] == 0) {
            table[index] = key;
        } else {
            int currentIndex = index;
            while (next[currentIndex] != -1) {
                currentIndex = next[currentIndex];
            }
            next[currentIndex] = size;
            table[size] = key;
        }
        size++;
    }

    // Other methods: search, delete, etc.
}

 我的其他博客

HTTP与HTTTPS的区别-CSDN博客

什么情况下会产生StackOverflowError（栈溢出）和OutOfMemoryError（堆溢出）怎么排查-CSDN博客

谈谈我对HashMap扩容机制的理解及底层实现-CSDN博客

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/230083.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

webpack该如何打包

webpack该如何打包

1.我们先创建一个空的大文件夹 2.打开该文件夹的终端 输入npm init -y 2.1.打开该文件夹的终端 2.2在该终端运行 npm init -y 3.安装webpack 3.1打开webpack网址 点击“中文文档” 3.2点击“指南”在点击“起步” 3.3复制基本安装图片画线的代码 4.在一开始的文件夹下在创建一…
阅读更多...
【性能测试】Jmeter 配置元件（一）：计数器

【性能测试】Jmeter 配置元件（一）：计数器

Jmeter 配置元件&#xff08;一&#xff09;&#xff1a;计数器 在 Jmeter 中&#xff0c;通过函数 ${__counter(,)} 可以实现每次加 1 1 1 的计数效果。但如果步长不为 1 1 1&#xff0c;则要利用到我们的计数器。 函数作用${__counter(,)}计数器&#xff0c;每次加 1${__d…
阅读更多...
int 和 Integer 有什么区别，还有 Integer 缓存的实现

int 和 Integer 有什么区别，还有 Integer 缓存的实现

✨前言✨   Java本文主要介绍Java int 和 Integer的区别以及Integer 缓存的实现 &#x1f352;欢迎点赞 &#x1f44d; 收藏 ⭐留言评论 &#x1f4dd;私信必回哟&#x1f601; &#x1f352;博主将持续更新学习记录收获&#xff0c;友友们有任何问题可以在评论区留言 文章目…
阅读更多...
AI别墅设计

AI别墅设计

这两年我致力于研发别墅AI自动化设计&#xff0c;包括设计别墅各层的平面图以及导出三维效果图。目的是可以快速生成大量别墅的设计图和效果图让自建房用户可以第一时间挑选自己需要的房型并看到房屋建成后效果&#xff0c;大大提高建筑施工和设计人员的工作效率。 别墅设计包括…
阅读更多...
记一次测试环境git翻车经历

记一次测试环境git翻车经历

本来想拉一个功能分支进行新的功能开发&#xff0c;合并代码发现没有冲突居然有文件被修改了&#xff0c;贸然选择最近的一次回滚提交&#xff0c;没想到不假思索的push -f 导致一部分dev主干的代码不见了。 事故记录 开发分支origin/dev&#xff0c;功能分支file 合并之后发…
阅读更多...
pytorch-mask-rcnn 官方

pytorch-mask-rcnn 官方

This is a Pytorch implementation 实现 of Mask R-CNN that is in large parts based on Matterports Mask_RCNN. Matterports repository is an implementation on Keras and TensorFlow. The following parts of the README are excerpts 摘录 from the Matterport README. …
阅读更多...
电子学会C/C++编程等级考试2021年09月（五级）真题解析

电子学会C/C++编程等级考试2021年09月（五级）真题解析

C/C++等级考试（1~8级）全部真题・点这里 第1题：抓牛 农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式： 1、从X移动到X-1或X+1，每次移动花费一分钟 2、从X移动到2*X，每…
阅读更多...
Gitlab+GitlabRunner搭建CICD自动化流水线将应用部署上Kubernetes

Gitlab+GitlabRunner搭建CICD自动化流水线将应用部署上Kubernetes

文章目录 安装Gitlab服务器准备安装版本安装依赖和暴露端口安装Gitlab修改Gitlab配置文件访问Gitlab 安装Gitlab Runner服务器准备安装版本安装依赖安装Gitlab Runner安装打包工具安装docker安装java17安装maven 注册Gitlab Runner 搭建自动化部署准备SpringBoot项目添加一个Co…
阅读更多...
【力扣热题100】287. 寻找重复数（弗洛伊德的乌龟和兔子方法）

【力扣热题100】287. 寻找重复数（弗洛伊德的乌龟和兔子方法）

【力扣热题100】287. 寻找重复数 写在最前面理解解决 "寻找重复数" 问题的算法问题描述弗洛伊德的乌龟和兔子方法为什么这个方法有效&#xff1f; 代码复杂度 总结回顾 写在最前面 刷一道力扣热题100吧 难度中等 https://leetcode.cn/problems/find-the-duplicate-…
阅读更多...
文献计量学方法与应用、主题确定、检索与数据采集、VOSviewer可视化绘图、Citespace可视化绘图、R语言文献计量学绘图分析

文献计量学方法与应用、主题确定、检索与数据采集、VOSviewer可视化绘图、Citespace可视化绘图、R语言文献计量学绘图分析

目录 一、文献计量学方法与应用简介 二、主题确定、检索与数据采集 三、VOSviewer可视化绘图 四、Citespace可视化绘图 五、R语言文献计量学绘图分析 六、论文写作 七、论文投稿 更多应用 文献计量学是指用数学和统计学的方法&#xff0c;定量地分析一切知识载体的交叉…
阅读更多...
HarmonyOS鸿蒙操作系统架构开发

HarmonyOS鸿蒙操作系统架构开发

什么是HarmonyOS鸿蒙操作系统&#xff1f; HarmonyOS是华为公司开发的一种全场景分布式操作系统。它可以在各种智能设备&#xff08;如手机、电视、汽车、智能穿戴设备等&#xff09;上运行&#xff0c;具有高效、安全、低延迟等优势。 目录 HarmonyOS 一、HarmonyOS 与其他操…
阅读更多...
用23种设计模式打造一个cocos creator的游戏框架----(十)迭代器模式

用23种设计模式打造一个cocos creator的游戏框架----(十)迭代器模式

1、模式标准 模式名称&#xff1a;迭代器模式 模式分类&#xff1a;行为型 模式意图&#xff1a;提供一种方法顺序访问一个聚合对象中的各个元素&#xff0c;且不需要暴露该对象的内部表示. 结构图&#xff1a; ​ 适用于&#xff1a; 1、当你需要遍历一个复杂的数据结构…
阅读更多...
24、文件上传漏洞——Apache文件解析漏洞

24、文件上传漏洞——Apache文件解析漏洞

文章目录 一、环境简介一、Apache与php三种结合方法二、Apache解析文件的方法三、Apache解析php的方法四、漏洞原理五、修复方法 一、环境简介 Apache文件解析漏洞与用户配置有密切关系。严格来说&#xff0c;属于用户配置问题&#xff0c;这里使用ubantu的docker来复现漏洞&am…
阅读更多...
概率测度理论方法（第 2 部分）

概率测度理论方法（第 2 部分）

一、说明 欢迎回到这个三部曲的第二部分&#xff01;在第一部分中&#xff0c;我们为测度论概率奠定了基础。我们探索了测量和可测量空间的概念&#xff0c;并使用这些概念定义了概率空间。在本文中&#xff0c;我们使用测度论来理解随机变量。 作为一个小回顾&#xff0c;在第…
阅读更多...
ardupilot开发 --- git 篇

ardupilot开发 --- git 篇

一些概念 工作区&#xff1a;就是你在电脑里能看到的目录&#xff1b;暂存区&#xff1a;stage区 或 index区。存放在 &#xff1a;工作区 / .git / index 文件中&#xff1b;版本库&#xff1a;本地仓库&#xff0c;存放在 &#xff1a;工作区 / .git 中 关于 HEAD 是所有本地…
阅读更多...
【js】js实现多个视频连续播放：

【js】js实现多个视频连续播放：

文章目录 一、效果&#xff1a;二、实现&#xff1a; 一、效果&#xff1a; 二、实现&#xff1a; <!DOCTYPE html> <html> <head><title>Video Player</title><style>#progressBar { width: 800px;height: 20px;background-color: #dd…
阅读更多...
图空图床图片外链系统源码-支持自定义权限策略-图片大小格式

图空图床图片外链系统源码-支持自定义权限策略-图片大小格式

含视频搭建教程。 大致功能&#xff1a; 支持本地等多种第三方云储存 AWS S3、阿里云 OSS、腾讯云 COS、七牛云、又拍云、SFTP、FTP、WebDav、Minio多种数据库驱动支持&#xff0c;MySQL 5.7、PostgreSQL 9.6、SQLite 3.8.8、SQL Server 2017支持配置使用多种缓存驱动&#xff…
阅读更多...
代立冬：基于Apache Doris+SeaTunnel 实现多源实时数据仓库解决方案探索实践

代立冬：基于Apache Doris+SeaTunnel 实现多源实时数据仓库解决方案探索实践

大家好&#xff0c;我是白鲸开源的联合创始人代立冬&#xff0c;同时担任 Apache DolphinScheduler 的 PMC chair 和 SeaTunnel 的 PMC。作为 Apache Foundation 的成员和孵化器导师&#xff0c;我积极参与推动多个开源项目的发展&#xff0c;帮助它们通过孵化器成长为 Apache …
阅读更多...
Java编程中通用的正则表达式（一）

Java编程中通用的正则表达式（一）

正则表达式&#xff08;Regular Expression&#xff0c;简称RegEx&#xff09;&#xff0c;又称常规表示法、正则表示、正规表示式、规则表达式、常式、表达式等&#xff0c;是计算机科学中的一个概念。正则表达式是用于描述某种特定模式的字符序列&#xff0c;特别是用来匹配、…
阅读更多...
软件工程复习

软件工程复习

一、题型 单项选择题 20分 填空题 10分 判断题 10分 简答题 18分 应用题 12分 综合题 30分 软件程序数据文档 软件是无形的、不可见的逻辑实体 20世纪60年代末爆发软件危机 软件危机是指软件在开发与维护过程中遇到的一系列严重的问题 …
阅读更多...
最新文章

Copyright @ 2022~2023