【数据结构】哈希表(hashTable)

2024-08-29 10:32

本文主要是介绍【数据结构】哈希表(hashTable),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

复习一下常见的数据结构与算法

文章目录

  • 一、走进哈希表(hashTable)
    • 1.哈希表的目的
    • 2.哈希表的设计原理
  • 二、哈希表的设计要素
    • 1.哈希函数-hash function
      • 基本概念
      • 优秀的哈希函数
      • Java中字符串的hash函数
    • 2.冲突解决方案-collision solution
      • 开散列
      • 闭散列
    • 3.重哈希-rehashing
      • 负载因子
      • 重哈希的描述
  • 三、简易实现
  • 四、参考资料

一、走进哈希表(hashTable)

1.哈希表的目的

实现数据的快速查找

2.哈希表的设计原理

image.png

二、哈希表的设计要素

  • 哈希函数-hash function
  • 冲突解决方案-collision solution
  • 重哈希-rehashing

1.哈希函数-hash function

基本概念

一个哈希函数需要具备如下特征:

  • 确定性
  • 不可逆

其输入为: 任意二进制数据,输出为:整数(Buckets的位置)

优秀的哈希函数

如何评价一个哈希函数是否优秀了?这里我们主要看:

  • 尽可能少的发生碰撞
  • 计算复杂度不要太高

常见的哈希函数包括:

  • 除余法modulo division
  • 平方取中法 mid square
  • 基数转换法 radix transformation

Java中字符串的hash函数

实现逻辑:

for(char c : str){hashCode = 31 * hashCode + c;
}

所以在Aa,BB、Ab,BC时会出现碰撞。通过如下测试代码可以发现,他们的hashCode是相同的。

 System.out.println("Aa".hashCode());System.out.println("BB".hashCode());

2.冲突解决方案-collision solution

开散列

open hashing, 又称拉链法 separate chaining

一言以蔽之,每个Bucket放的都是一个链表头结点的引用,假如冲突了就在这个链表后面加一个结点即可。(链表,往下拉)

闭散列

closed hashing,又称开址法 open addressing

当前位置已有其他元素后,再通过新算法为其找新的位置,(如这个位置的下一个空位).

(有哪些常见的查找新位置的算法呢?线性探查,待补充!)

3.重哈希-rehashing

哈希表扩缩容时,需要对已有数据的位置进行重新编排,这个就是常说的重哈希。

负载因子

负载因子load factor,等于哈希表元素的个数/哈希表容量,用于描述哈希表当前的负载。
一般当负载因子大于0.5的时候,检索性能急剧下降,冲突概率变高,此时一般就要进行哈希表扩容与重哈希了。

重哈希的描述

  • 调整哈希表的大小,并将元素重新摆放。
  • 当哈希表过于稀疏,进行重哈希可以节省空间
  • 当哈希表过于稠密,进行哈希可以加速查找( 空间换时间)

三、简易实现

四、参考资料

九章算法
算法导论
MIT-算法导论课程

这篇关于【数据结构】哈希表(hashTable)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1117604

相关文章

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

哈希表的底层实现(1)---C++版

目录 哈希表的基本原理 哈希表的优点 哈希表的缺点 应用场景 闭散列法 开散列法 开放定值法Open Addressing——线性探测的模拟实现 超大重点部分评析 链地址法Separate Chaining——哈希桶的模拟实现 哈希表(Hash Table)是一种数据结构,它通过将键(Key)映射到值(Value)的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希

哈希表的封装和位图

文章目录 2 封装2.1 基础框架2.2 迭代器(1)2.3 迭代器(2) 3. 位图3.1 问题引入3.2 左移和右移?3.3 位图的实现3.4 位图的题目3.5 位图的应用 2 封装 2.1 基础框架 文章 有了前面map和set封装的经验,容易写出下面的代码 // UnorderedSet.h#pragma once#include "HashTable.h"

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

PHP: 深入了解一致性哈希

前言 随着memcache、redis以及其它一些内存K/V数据库的流行,一致性哈希也越来越被开发者所了解。因为这些内存K/V数据库大多不提供分布式支持(本文以redis为例),所以如果要提供多台redis server来提供服务的话,就需要解决如何将数据分散到redis server,并且在增减redis server时如何最大化的不令数据重新分布,这将是本文讨论的范畴。 取模算法 取模运