精华内容
下载资源
问答
  • 哈希表数据结构实现代码,符合ADT要求,头文件放ADT函数接口定义和存储结构定义,cpp文件放实现,在控制台查看输出,C语言实现,功能多,注释多,轻松易懂,可用来初学或者作业完成
  • 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。 [测试数据] 取读者周围较熟悉的30个人名
  • /******************* 数据结构哈希表算法实现 ********************/
  • JavaScript实现哈希表数据结构

    千次阅读 2018-07-10 08:13:27
    一、简单说明1、JavaScript是没有哈希表数据结构的,那么当我们需要用到类似哈希表这样的键值对数据结构时怎么办?答案就是自己实现一个,我们可以利用JavaScript的一些特性来实现自己的哈希表数据结构。2、首先,...

    一、简单说明

    1、JavaScript是没有哈希表数据结构的,那么当我们需要用到类似哈希表这样的键值对数据结构时怎么办?答案就是自己实现一个,我们可以利用JavaScript的一些特性来实现自己的哈希表数据结构。

    2、首先,哈希表是一种键值对数据结构,键是唯一的,这个特征跟JavaScript的Object对象有点类似,Object对象的属性是唯一的,属性和值的映射就像是键值对一样,那么我们可以用一个Object对象来代表键值对的存储,再加上一个size变量用来记录键值对的数量,这样简单的键值对存储结构就有了。

    3、其次,哈希表有哪些常用的方法:

         put  ->  往哈希表放入一个键值对

         get  ->  从哈希表获取一个指定键的值

         remove  ->  从哈希表删除指定键关联的键值对

         getSize  ->  获取哈希表键值对数量

         clear  ->  清空哈希表中的所有键值对

         containsKey  ->  判断哈希表是否存在指定的键

         containsValue  ->  判断哈希表是否存在指定的值

         getKeys  ->  获取哈希表中所有的键列表

         getValues  ->  获取哈希表中所有键值对的值列表

    4、上述第三点各个方法的实现如代码所示。



    二、代码实现如下

    /**
     * 实现哈希表的数据结构
     */
    function HashTable() {
    	var size = 0;
    	var entry = new Object();
    	
    	// 增加键值对
    	this.put = function(key, value) {
    		// 已存在key则更新value,否则新增
    		if (!this.containsKey(key)) {
    			++size;
    		}
    		entry[key] = value;
    	};
    	
    	// 获取键对应的值
    	this.get = function(key) {
    		return (this.containsKey(key) ? entry[key] : null);
    	};
    
    	// 删除指定键对应的值
    	this.remove = function(key) {
    		if (this.containsKey(key) && (delete entry[key])) {
    			--size;
    		}
    	};
    	
    	// 判断一个key是否存在
    	this.containsKey = function(key) {
    		return (key in entry);
    	};
    	
    	// 判断一个value是否存在
    	this.containsValue = function (value) {
    		for (var key in entry) {
    			if (entry[key] == value) {
    				return true;
    			}
    		}
    		return false;
    	};
    	
    	// 返回哈希表的所有key
    	this.getKeys = function() {
    		var keys = new Array();
    		for (var key in entry) {
    			keys.push(key);
    		}
    		return keys;
    	};
    	
    	// 返回哈希表的所有value
    	this.getValues = function() {
    		var values = new Array();
    		for (var key in entry) {
    			values.push(entry[key]);
    		}
    		return values;
    	};
    	
    	// 返回哈希表键值对数量
    	this.getSize = function() {
    		return size;
    	};
    	
    	// 清空哈希表
    	this.clear = function() {
    		size = 0;
    		entry = new Object();
    	};
    }
    
    
    /*--- 以下为测试数据 ---*/
    
    // 初始化一个hashTable对象
    var hashtable = new HashTable();
    
    // 打印hashTable的所有key
    console.log(hashtable.getKeys());
    
    // 打印hashTable的所有key
    hashtable.put("name", "Edward");
    hashtable.put("age", 5);
    
    // 获取键值对数量
    console.log(hashtable.getSize());
    // 打印hashTable的所有key
    console.log(hashtable.getKeys());
    
    // 获取指定key的值
    console.log(hashtable.get("name"));
    console.log(hashtable.get("email"));
    
    hashtable.clear();
    // 获取键值对数量
    console.log(hashtable.getSize());
    // 打印hashTable的所有key
    console.log(hashtable.getKeys());




    展开全文
  • 哈希表 这包含我在天普大学上课的哈希表数据结构
  • 数据结构哈希表

    2015-01-20 10:13:26
    数据结构输出一个哈希表,这是我自己写的程序,输出完全没有问题,用C++编写,安全可靠。
  • 哈希表 JavaScript中的数据结构实现。 根据哈希函数返回的哈希码将条目(键,值)存储在存储桶中。 如果哈希码发生冲突,则条目将存储在存储桶中的数组中,并通过唯一的键值进行检索。 安装 npm install ...
  • 含需求分析、概要设计、详细设计、调试分析、使用说明、测试结果、附件。...待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。
  • 哈希表 这是哈希表数据结构的简单实现
  • 哈希表数据结构

    2020-06-06 22:35:52
    哈希表(Hash table,也叫散列表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射...

    转载自:https://www.jianshu.com/p/b468abd86f61

    Hash表的结构图:

    在这里插入图片描述

    数组 + 链表

    哈希表(Hash table,也叫散列表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表

    白话一点的说就是通过把Key通过一个固定的算法函数(hash函数)转换成一个整型数字,然后就对该数字对数组的长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。

    当使用hash表查询时,就是使用hash函数将key转换成对应的数组下标,并定位到该下标的数组空间里获取value,这样就充分利用到数组的定位性能进行数据定位。

    先了解一下下面几个常说的几个关键字是什么:

    • key:我们输入待查找的值
    • value:我们想要获取的内容
    • hash值:key通过hash函数算出的值(对数组长度取模,便可得到数组下标)
    • hash函数(散列函数):存在一种函数F,根据这个函数和查找关键字key,可以直接确定查找值所在位置,而不需要一个个遍历比较。这样就预先知道key在的位置,直接找到数据,提升效率。
    • 地址index=F(key)

    hash函数就是根据key计算出该存储地址的位置,hash表就是基于hash函数建立的一种查找表。

    展开全文
  • 现在只能实现关键字为数字,存储单位为为字符串类型的,给大家简单的提供下HASH的存储原理
  • 哈希表(hash table),这种数据结构提供了键(Key)和值 (Value)的映射关系;只要给出一个Key,就可以高效查找到它所匹配的Value,时间复杂度接近于O(1) 2、哈希函数 散列表在本质上也是一个数组,可是数组只能...

    1、什么是哈希表

    哈希表(hash table),这种数据结构提供了键(Key)和值 (Value)的映射关系;只要给出一个Key,就可以高效查找到它所匹配的Value,时间复杂度接近于O(1)
    在这里插入图片描述

    2、哈希函数

    散列表在本质上也是一个数组,可是数组只能根据下标,像a[0]、a[1]、a[2]、a[3]、a[4]这样来访问,而散列表的Key则是以字符串类型为主的,例如以学生的学号作为Key,输入002123,查询到李四;或者以单词为Key,输入by,查询到数字46……所以需要一个“中转站”,通过某种方式,把Key和数组下标进行转换,这个中转站就叫作哈希函数。
    在这里插入图片描述

    哈希函数的实现

    以Java的常用集合HashMap为例,来讲解哈希函数在Java中的实现:
    在Java及大多数面向对象的语言中,每一个对象都有属于自己的hashcode,这个hashcode是区分不同对象的重要标识,无论对象自身的类型是什么,它们的 hashcode都是一个整型变量。
    既然都是整型变量,想要转化成数组的下标简单的转化方式就是按照数组长度进行取模运算

    index = HashCode (Key) % Array.length

    通过哈希函数**可以把字符串或其他类型的Key,转化成数组的下标 index;**例如给出一个长度为8的数组,则当 key=001121时,index = HashCode (“001121”) % Array.length = 1420036703 % 8 = 7
    而当key=this时,index = HashCode (“this”) % Array.length = 3559070 % 8 = 6

    3、哈希表的读写操作

    写操作(put)

    写操作就是在散列表中插入新的键值对,如调用 hashMap.put(“002931”, “王五”),意思是插入一组Key为002931、 Value为王五的键值对;具体步骤如下:

    • 第1步,通过哈希函数,把Key转化成数组下标5;
    • 第2步,如果数组下标5对应的位置没有元素,就把这个Entry填充到数组下标5的位置;
      在这里插入图片描述
      由于数组的长度是有限的,当插入的Entry越来越多时,不同的Key通过哈希函数获得的下标有可能是相同的;例如002936这个Key对应的数组下标是2; 002947这个Key对应的数组下标也是2;这种情况称为哈希冲突
      在这里插入图片描述
      哈希冲突是无法避免的,解决哈希冲突的方法主要有两种,一种是开放寻址法,一种是链表法;
    • 开放寻址法
      当一个Key通过哈希函数获得对应的数组下标已被占用时,我们可以“另谋高就”,寻找下一个空档位置,以上面的情况为例,Entry6通过哈希函数得到下标 2,该下标在数组中已经有了其他元素,那么就向后移动1位,看看数组下标3的位置是否有空:
      在这里插入图片描述
      很不巧,下标3也已经被占用,那么就再向后移动1位,看看数组下标4的位置是否有空:
      在这里插入图片描述
      幸运的是,数组下标4的位置还没有被占用,因此把Entry6存入数组下标4的位置:
      在这里插入图片描述
      这就是开放寻址法的基本思路!在Java中,ThreadLocal 所使用的就是开放寻址法。
    • 链表法
      链表法被应用在了Java的集合类HashMap当中,HashMap数组的每一个元素不仅是一个Entry对象,还是一个链表的头节点,每 一个Entry对象通过 next 指针指向它的下一个Entry节点,当新来的 Entry映射到与之冲突的数组位置时,只需要插入到对应的链表中即可。
      在这里插入图片描述

    读操作(get)

    读操作就是通过给定的Key,在散列表中查找对应的Value;例如调用 hashMap.get(“002936”),意思是查找Key为002936的Entry在散列表中所对应的值,步骤如下:

    • 第1步,通过哈希函数,把Key转化成数组下标2;
    • 第2步,找到数组下标2所对应的元素,如果这个元素的Key是002936,那么就找到了;如果这个Key不是002936也没关系,由于数组的每个元素都与一个链表对应,可以顺着链表慢慢往下找,看看能否找到与Key相匹配的节点。
      在这里插入图片描述
      在上图中,首先查到的节点Entry6的Key是002947,和待查找的Key002936不符;接着定位到链表下一个节点Entry1,发现Entry1的Key 002936正是要寻找的,所以返回Entry1的Value即可。

    扩容(resize)

    什么时候需要进行扩容呢?
    当经过多次元素插入,散列表达到一定饱和度时,Key映射位置发生冲突的概率会逐渐提高;大量元素拥挤在相同的数组下标位置,形成很长的链表, 对后续插入操作和查询操作的性能都有很大影响
    在这里插入图片描述
    这种情况下,散列表就需要扩展它的长度,也就是进行扩容;对于JDK中的散列表实现类HashMap来说,影响其扩容的因素有两个:

    • Capacity,即HashMap的当前长度;
    • LoadFactor,即HashMap的负载因子,默认值为0.75f

    衡量HashMap需要进行扩容的条件:HashMap.Size >= Capacity × LoadFactor
    注意:扩容不是简单地把散列表的长度扩大,而是经历了下面两个步骤:

    • 1.扩容,创建一个新的Entry空数组,长度是原数组的2倍;
    • 2.重新Hash,遍历原Entry数组,把所有的Entry重新Hash到新数组中;
    • 为什么要重新Hash呢?因为长度扩大以后,Hash的规则也随之改变
      经过扩容,原本拥挤的散列表重新变得稀疏,原有的Entry也重新得到了尽可能均匀的分配,扩容前HashMap如下:
      在这里插入图片描述
      扩容后的 HashMap 如下:
      在这里插入图片描述

    关于HashMap的实现,JDK 8和以前的版本有着很大的不同。当多个Entry被Hash到同一个数组下标位置时,为了提升插入和查找的效率,HashMap 会把Entry的链表转化为红黑树这种数据结构

    4、总结

    • 什么是数组
      数组是由有限个相同类型的变量所组成的有序集合,它的物理存储方式是顺序存储,访问方式是随机访问;利用下标查找数组元素的时间复杂度是O(1),中间插入、删除数组元素的时间复杂度是O(n)
    • 什么是链表
      链表是一种链式数据结构,由若干节点组成,每个节点包含指向下一节点的指针,链表的物理存储方式是随机存储,访问方式是顺序访问。查找链表节点的时间复杂度是O(n),中间插入、删除节点的时间复杂度是O(1)
    • 什么是栈
      栈是一种线性逻辑结构,可以用数组实现,也可以用链表实现。栈包含入栈和出栈操作,遵循先入后出的原则(FILO)。
    • 什么是队列
      队列也是一种线性逻辑结构,可以用数组实现,也可以用链表实现。队列包含 入队和出队操作,遵循先入先出的原则(FIFO)。
    • 什么是哈希表
      哈希表是存储Key-Value映射的集合;对于某一个Key,散列表可以在接近O(1)的时间内进行读写操作。散列表通过哈希函数实现Key和数组下标的 转换,通过开放寻址法和链表法来解决哈希冲突。
      —————————————————————————————————————————————
      内容来源:《漫画算法》
    展开全文
  • 哈希表课程设计

    2015-07-05 16:13:23
    (1) 设每个记录有下列数据项:手机号码、姓名、性别、E-mail地址。 (2) 从文件读入各记录,以手机号码为关键字建立散列表(长度为43)。采用开放定址法建立散列表。 (3)显示开放定址散列表最高的寻址次数,若...
  • 数据结构哈希表

    万次阅读 多人点赞 2019-05-26 17:40:18
    哈希表散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录...
    哈希表的相关学习:

    哈希表

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

    给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

    哈希函数

    哈希表是时间与空间之间的平衡,因此哈希函数的设计很重要。所以哈希函数应该尽量减少Hash冲突。也就是说“键”通过哈希函数得到的“索引”分布越均匀越好。

    整形

    对于小范围的整数比如-100~100,我们完全可以对整数直接使用把它映射到0~200之间,而对于身份证这种的大整数,通常我们采用的是取模,比如大整数的后四位相当于mod 10000,这里有一个小问题,如果我们选择的数字如果不好的话,就有可能可能导致数据映射分布不均匀,因此我们最好寻找一个素数.

    如果选择一个合适的素数呢,这里有一个选择:

    图片来源:https://planetmath.org/goodhashtableprimes

    浮点型

    在计算机中都是32位或者64位的二进制表表示,只不过计算j级解析成了浮点数

    字符串

    字符串我们需要把它也转成整型处理

    我们对上面的方法进行优化一下,这就涉及到数学方面的知识了

    对于字符串来说,计算出来的大整形如果特别大的话可能会出现内存溢出,因此我们可以对取模的过程分别挪到式子里面.

    对于整个字符串来说我们可以写程序也是十分容易地写出来他的处理函数

    1
    2
    3
    int hash = 0;
    for (int i = 0; i < s.length; i++) {
    hash = (hash * B + s.charAt(i)) % M;

    案例

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    public class Student {

    int grade;
    int cls;
    String firstName;
    String lastName;

    Student(int grade, int cls, String firstName, String lastName){
    this.grade = grade;
    this.cls = cls;
    this.firstName = firstName;
    this.lastName = lastName;
    }

    @Override
    public int hashCode(){

    int B = 31;
    int hash = 0;
    hash = hash * B + ((Integer)grade).hashCode();
    hash = hash * B + ((Integer)cls).hashCode();
    hash = hash * B + firstName.toLowerCase().hashCode();
    hash = hash * B + lastName.toLowerCase().hashCode();
    return hash;
    }

    //重写
    @Override
    public boolean equals(Object o){

    if(this == o)
    return true;

    if(o == null)
    return false;

    if(getClass() != o.getClass())
    return false;

    Student another = (Student)o;
    return this.grade == another.grade &&
    this.cls == another.cls &&
    this.firstName.toLowerCase().equals(another.firstName.toLowerCase()) &&
    this.lastName.toLowerCase().equals(another.lastName.toLowerCase());
    }

    @Override
    public String toString() {
    return "Student{" +
    "grade=" + grade +
    ", cls=" + cls +
    ", firstName='" + firstName + '\'' +
    ", lastName='" + lastName + '\'' +
    '}';
    }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    import java.util.HashSet;
    import java.util.HashMap;

    public class Main {

    public static void main(String[] args) {

    int a = 42;
    System.out.println(((Integer)a).hashCode());

    int b = -42;
    System.out.println(((Integer)b).hashCode());

    double c = 3.1415926;
    System.out.println(((Double)c).hashCode());

    String d = "imooc";
    System.out.println(d.hashCode());

    System.out.println(Integer.MAX_VALUE + 1);
    System.out.println();

    Student student = new Student(3, 2, "penghui", "Han");
    System.out.println(student.hashCode());

    HashSet<Student> set = new HashSet<>();
    set.add(student);
    for (Student s : set) {
    System.out.println(s.toString());

    }

    HashMap<Student, Integer> scores = new HashMap<>();
    scores.put(student, 100);
    System.out.println(scores.toString());

    Student student2 = new Student(3, 2, "Penghui", "han");
    System.out.println(student2.hashCode());
    System.out.println(student.equals(student2));
    }
    }

    我们可以看到在实际的运行过程中对于整数的负数来说,依旧存在整数类型int中,对于浮点数和字符串来说都有都i是按照上面的方法.来进行计算。对于hashCode值相同我们并没有办法取判断是否属于一个对象,因此在equals和hashCode相同鼓的时候我们才能够说这个两个对象是相同的。

    哈希冲突处理

    链地址法

    哈希表本质就是一个数组,

    对于哈希表我们只需要让他求出K1然后在模于M,当然这个大M是一个素数。对于负数来说,可以直接用绝对值来解决负数的问题。

    当然我们有时候看别人的代码或者源码的时候会看到

    用16进制法表示的整型,先和一个16进制表示的0x7fffffff的结果我们在对M取模,这个表示的是用二进制表示的话是31个1,整型有32位,最高位是符号位,32位和31位相与,这样做是吧最高位的32位,模成了0,符号位的问题我们就解决了。因此如果我们记录的k1的值为4,那么我们就可可以把k1存储到地址4这个位置中去。

    如果k2的索引位置为1,那么假设k3的位置也为1,那么我们就产生了hash冲突,如何解决呢?

    这里我们可以采用链表的方式,对于整个哈希表我们开M个空间,由于会出现hash冲突,我们可以把它做成链表,这种方法也叫separate chaining,当然我们已可以存红黑树,或者TreeMap。

    本质上来说,HashMap就是一个TreeMap数组,HashSet就是一个TreeSet数组。对于Java8来说,Java8之前每一个位置对应的是一个链表,Java8开始之后,当哈希冲突达到了一定的程度,每一个位置从链表转化为红黑树,这个阈值为8;

    代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    import java.util.LinkedList;
    import java.util.List;

    public class HashTable<T>{
    public HashTable() {
    this(DEFAULT_TABLE_SIZE);
    }
    public HashTable(int size) {
    theLists=new LinkedList[nextPrime(size)];
    for(int i=0;i<theLists.length;i++) {
    theLists[i]=new LinkedList<>();//初始化链表数组
    }
    }

    /*
    * 哈希表插入元素
    * */
    public void insert(T x) {
    List<T> whichList=theLists[myhash(x)];
    /*
    * 如果当前哈希地址的链表不含有元素,则链表中添加该元素
    * */
    if(!whichList.contains(x)) {
    whichList.add(x);
    if(++currentSize>theLists.length)//如果表长度不够,则扩容
    rehash();
    }
    }
    public void remove(T x) {
    List<T> whichList=theLists[myhash(x)];
    if(whichList.contains(x)) {
    whichList.remove(x);
    currentSize--;
    }
    }
    public boolean contains(T x) {
    List<T> whilchList=theLists[myhash(x)];
    return whilchList.contains(x);
    }
    public void makeEmpty() {
    for(int i=0;i<theLists.length;i++)
    theLists[i].clear();
    currentSize=0;
    }

    private static final int DEFAULT_TABLE_SIZE=101;

    private List<T> [] theLists;
    private int currentSize;

    /*
    * 哈希表扩容,表长度为下一个素数
    * */
    private void rehash() {
    List<T>[] oldLists=theLists;
    theLists=new List[nextPrime(2*theLists.length)];
    for(int j=0;j<theLists.length;j++)
    theLists[j]=new LinkedList<>();

    currentSize=0;
    /*
    * 更新哈希表
    * */
    for(List<T> list:oldLists)
    for(T item:list)
    insert(item);
    }
    /*
    * myhash()方法获得哈希表的地址
    * */
    private int myhash(T x) {
    int hashVal=x.hashCode();//hashCode()方法返回该对象的哈希码值
    hashVal%=theLists.length;//对哈希表长度取余数
    if(hashVal<0)
    hashVal+=theLists.length;
    return hashVal;
    }
    //下一个素数
    private static int nextPrime(int n) {
    if( n % 2 == 0 )
    n++;

    for( ; !isPrime( n ); n += 2 )
    ;

    return n;
    }
    //判断是否是素数
    private static boolean isPrime(int n) {
    if( n == 2 || n == 3 )
    return true;

    if( n == 1 || n % 2 == 0 )
    return false;

    for( int i = 3; i * i <= n; i += 2 )
    if( n % i == 0 )
    return false;

    return true;
    }
    }

    开放地址法

    这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述:
    H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ( k ≤ m – 1))
    其中: H ( key ) 为关键字 key 的直接哈希地址, m 为哈希表的长度, di 为每次再探测时的地址增量。
    采用这种方法时,首先计算出元素的直接哈希地址 H ( key ) ,如果该存储单元已被其他元素占用,则继续查看地址为 H ( key ) + d 2 的存储单元,如此重复直至找到某个存储单元为空时,将关键字为 key 的数据元素存放到该单元。
    增量 d 可以有不同的取法,并根据其取法有不同的称呼:
    ( 1 ) d i = 1 , 2 , 3 , …… 线性探测再散列;
    ( 2 ) d i = 1^2 ,- 1^2 , 2^2 ,- 2^2 , k^2, -k^2…… 二次探测再散列;
    ( 3 ) d i = 伪随机序列 伪随机再散列;

    例1设有哈希函数 H ( key ) = key mod 7 ,哈希表的地址空间为 0 ~ 6 ,对关键字序列( 32 , 13 , 49 , 55 , 22 , 38 , 21 )按线性探测再散列和二次探测再散列的方法分别构造哈希表。
    解:
    ( 1 )线性探测再散列:
    32 % 7 = 4 ; 13 % 7 = 6 ; 49 % 7 = 0 ;
    55 % 7 = 6 发生冲突,下一个存储地址( 6 + 1 )% 7 = 0 ,仍然发生冲突,再下一个存储地址:( 6 + 2 )% 7 = 1 未发生冲突,可以存入。
    22 % 7 = 1 发生冲突,下一个存储地址是:( 1 + 1 )% 7 = 2 未发生冲突;
    38 % 7 = 3 ;
    21 % 7 = 0 发生冲突,按照上面方法继续探测直至空间 5 ,不发生冲突,所得到的哈希表对应存储位置:
    下标: 0 1 2 3 4 5 6

    49 55 22 38 32 21 13

    当然还有其他的方法比如再哈希法,Coalesced Hashing法(综合了Seperate Chainging 和 Open Addressiing)等。

    代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    class DataItem { //数据                             
    private int iData; // data item (key)

    public DataItem(int ii) {
    iData = ii;
    }
    public int getKey(){
    return iData;
    }

    }

    class HashTable{//数组实现的哈希表,开放地址法之线性探测
    private DataItem[] hashArray; //存放数据的数组
    private int arraySize;
    private DataItem nonItem; //用作删除标志

    public HashTable(int size) {//构造函数
    arraySize = size;
    hashArray = new DataItem[arraySize];
    nonItem = new DataItem(-1); // deleted item key is -1
    }

    public void displayTable(){//显示哈希表
    System.out.print("Table: ");
    for(int j=0; j<arraySize; j++)
    {
    if(hashArray[j] != null)
    System.out.print(hashArray[j].getKey() + " ");
    else
    System.out.print("** ");
    }
    System.out.println("");
    }

    //哈希函数
    public int hashFunc(int key)
    {
    return key % arraySize;
    }


    //在哈希表中插入数据
    public void insert(DataItem item){
    int key = item.getKey(); // 获取数据的键值
    int hashVal = hashFunc(key); // 计算其哈希值

    while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1){
    ++hashVal; // 插入位置被占,线性探测下一位置
    hashVal %= arraySize; // 不让超过数组的大小
    }
    hashArray[hashVal] = item; // 找到空位后插入
    }

    //在哈希表中删除
    public DataItem delete(int key) {
    int hashVal = hashFunc(key); // 计算其哈希值

    while(hashArray[hashVal] != null){
    if(hashArray[hashVal].getKey() == key){
    DataItem temp = hashArray[hashVal]; // 记录已删除的数据
    hashArray[hashVal] = nonItem; // 删除它
    return temp;
    }
    ++hashVal; // 到下一单元找
    hashVal %= arraySize;
    }
    return null; // 没有找到要删除的数据
    }

    //在哈希表中查找
    public DataItem find(int key) {
    int hashVal = hashFunc(key); //哈希这个键

    while(hashArray[hashVal] != null) { // 直到空的单元
    if(hashArray[hashVal].getKey() == key)
    return hashArray[hashVal]; // 找到
    ++hashVal; // 去下一单元找
    hashVal %= arraySize; // 不让超过数组的大小
    }
    return null; // 没有找到
    }

    }

    参考资料

    https://www.cnblogs.com/vincentme/p/7920237.html

    https://blog.csdn.net/w_fenghui/article/details/2010387

    https://128kj.iteye.com/blog/1744810

    展开全文
  • 1、讲解和演示哈希表的建立和数据查询功能的实现原理; 2、讲解和演示哈希表用于映射类(CMap)的开发方法;
  • 该包包含以下常见数据结构的基于 MATALB 类的实现: 1) 数组2) 二叉搜索树3) 哈希表4) 堆5) 列表6) 队列7) 红黑树8) 堆栈 代码的编写方式使其可以轻松翻译成其他语言。 大多数方法取自规范算法文本: 算法导论...
  • JAVA数据结构哈希表

    千次阅读 2018-09-02 10:50:21
    hash比树形结构快的原因,的是位置是计算出来的通过hash函数,满足随机插入的结构。但是在有该优点的情况下,需要考虑哈希冲突 本例结构中采用链地址法【在hash的每一个单元,都是链表结构,发生冲突的...
  • 数据结构-哈希表理解与实现

    千次阅读 2018-01-23 18:07:59
    一、哈希表的简介 1、在我们C++11中的unordered_set/unordered_map以及unordered_multiset/unordered_multimap底层最主要的实现就是哈希表;而哈希表则是通过关键字(key)按照一定的规律映射到表中的位置。 2、...
  • 哈希表 数据结构 课程设计 C++ 报告 资源整合 希望支持
  • 【算法与数据结构 10】哈希表——高效查找的利器

    千次阅读 多人点赞 2020-09-24 17:03:21
    大家都在看的高效《数据结构与算法》!
  • java数据结构——哈希表

    千次阅读 2018-10-13 09:42:53
    哈希表,是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表,也称为哈希表。...
  • JS实现常见数据结构哈希表

    千次阅读 2019-10-19 17:17:08
    哈希表特点:存储键值对的数据结构哈希表内部是使用一个hash函数把传入的键转换成一串数字,而这串数字将作为键值对实际的key,通过这个key查询对应的value非常快。 哈希表方法: 1. add:添加一组键值对。 2. ...
  • 设有若干个学生的考试成绩,采用除留余数求哈希地址,将学生的信息存储到该地址空间,并且采用线性探测法解决冲突问题。
  • 散列表的设计实验报告 1题目 散列表的设计:针对某个集体中人名设计一个散列表使得平均查找长度不超过R,并完成相应的建表和查表程序 2基本要求 假设人名为中国人姓名的汉语拼音形式待填入哈希表的人名共30个取平均...
  • 数据结构---哈希表的C语言实现

    万次阅读 多人点赞 2018-03-06 17:58:46
    说到哈希表,,首先就得说到哈希函数,哈希函数是用来得到给定key值的在哈希表中的存储位置的。 哈希函数也并不是固定的,可以自己根据情况来定,一般常用常见的有直接定制法,除留余数法,平方取中法,折叠法,...
  • python中的哈希表数据结构

    千次阅读 2019-04-24 09:44:15
    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • 数据结构哈希表(HASH)

    万次阅读 多人点赞 2018-01-18 19:15:38
    在顺序中查找时,需要从表头开始,依次遍历比较a[i]与key的值是否相等,直到相等才返回索引i;在有序中查找时,我们经常使用的是二分查找,通过比较key与a[i]的大小来折半查找,直到相等时才返回索引i。最终通过...
  • 数据结构——哈希表的详解与实现

    千次阅读 2020-08-07 21:30:41
    数据结构——哈希表(HashTable) 1.前言 ​ 当我们频繁的查找数据中的某个元素时,我们通常会选择数组来存放数据,因为数组的的内存是连续的,可以直接通过下标访问数据,但是它添加和删除数据比较麻烦;虽然链表...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 215,410
精华内容 86,164
关键字:

哈希表数据结构

数据结构 订阅