精华内容
下载资源
问答
  • 哈希表数据结构

    2020-07-05 22:08:23
  • Python实现哈希表,Python完成哈希表数据结构

    阅读目录

    概述

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

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

    Python实现

    • 以google一个题目的实现来体会什么是哈希表:
      在这里插入图片描述
      在这里插入图片描述
    • 思路图
      在这里插入图片描述
    • 需要创建三个类:HashTable类(主要操作的类),Employee类(录入员工信息)、EmpLinkList类(用链表串联起每一个员工的信息)

    初步完成

    # 雇员类
    class Employee(object):
        def __init__(self, emp_id, emp_name):
            self.emp_id = emp_id
            self.emp_name = emp_name
            self.next = None
    
    
    # 创建hashtable 管理多条链表
    class HashTable(object):
        def __init__(self, size):
        	# 不好意思,请让我先花里胡哨一把,哈哈哈
            self.menu = [k for k in HashTable.__dict__ if not (k.startswith("__") and k.endswith("__"))][:-1]  # 获取类中的方法
            self.size = size  # 表示有多少条链表
            self.__emp_link_array = [None] * size  # 初始化一个列表,容量大小靠传入
            for i in range(self.size):  # 初始化每个链表
                self.__emp_link_array[i] = EmpLinkList()
    
        def add(self, emp):  # 传入一个Employee类封装的对象
            # 根据 员工的id,得到该员工应该加入哪条链表
            emp_link_list_no = self.hash_fun(emp.emp_id)
            # 将 emp 添加到对应的链表中
            self.__emp_link_array[emp_link_list_no].add(emp)
    
        # 遍历出所有链表
        def travel_link(self):
            for i in range(self.size):
                self.__emp_link_array[i].travel(i)
    
        # 编写散列函数,使用一个简单的取模法
        def hash_fun(self, temp_id):
            return temp_id % self.size
    
    
    # 创建 EmployeeLinklist 表示链表
    class EmpLinkList(object):
        def __init__(self):
            self.__head = None
    
        # 添加雇员到链表
        def add(self, emp):
            # 假定,当添加雇员时,id是自增长,即id的分配总是从小到大
            # 因此我们将该雇员直接加入到本链表的最后 即可
            if self.__head is None:
                self.__head = emp
                return  # 注意这个return
            # 如果不是添加第一个雇员,需要建立一个辅助指针,定位到最后
            cur = self.__head
            while cur.next is not None: # 注意是 cur.next
                cur = cur.next
            cur.next = emp
    
        def travel(self, no):
            if self.__head is None:
                print("第 %d 链表为空" % (no + 1))
                return
            print("第 %d 链表信息为:" % (no + 1))
            cur = self.__head
            while cur is not None:
                print('=>id = %d name = %s' % (cur.emp_id, cur.emp_name))
                cur = cur.next
            print()
    
    
    if __name__ == '__main__':
        hashtable = HashTable(7)  # 创建哈希表
        while True:
            for no, item in enumerate(hashtable.menu):
                print("%d : %s 功能" % (no + 1, item))
            active_no = int(input("请输入你要执行的功能:"))
            active = getattr(hashtable, hashtable.menu[active_no - 1]) # 用反射
            if active_no == 1:
                emp_id = int(input("请输入员工id:"))
                emp_name = input("请输入员工姓名:")
                emp_obj = Employee(emp_id, emp_name)
                active(emp_obj)
            else:
                active()
    
    • 测试结果
      在这里插入图片描述

    完整实现

    # 雇员类
    class Employee(object):
        def __init__(self, emp_id, emp_name):
            self.emp_id = emp_id
            self.emp_name = emp_name
            self.next = None
    
    
    # 创建hashtable 管理多条链表
    class HashTable(object):
        def __init__(self, size):
            self.menu = [k for k in HashTable.__dict__ if not (k.startswith("__") and k.endswith("__"))][:-1]  # 获取类中的方法
            self.size = size  # 表示有多少条链表
            self.__emp_link_array = [None] * size  # 初始化一个列表,容量大小靠传入
            for i in range(self.size):  # 初始化每个链表
                self.__emp_link_array[i] = EmpLinkList()
    
        def add(self, emp):  # 添加雇员,传入一个Employee类封装的对象
            # 根据 员工的id,得到该员工应该加入哪条链表
            emp_link_list_no = self.hash_fun(emp.emp_id)
            # 将 emp 添加到对应的链表中
            self.__emp_link_array[emp_link_list_no].add(emp)
    
        def travel_link(self):  # 遍历出所有链表
            for i in range(self.size):
                self.__emp_link_array[i].travel(i)
    
        def find_emp(self, went_id):  # 查找雇员
            emp_link_list_no = self.hash_fun(went_id)
            emp = self.__emp_link_array[emp_link_list_no].find_emp_info(went_id)
            if emp is not None:
                print("在第%d条链表中找到了 雇员 id= %d\n" % ((emp_link_list_no + 1), went_id))
            else:
                print("在哈希表中不存在,没有找到该雇员")
    
        # 编写散列函数,使用一个简单的取模法
        def hash_fun(self, temp_id):
            return temp_id % self.size
    
    
    # 创建 EmployeeLinklist 表示链表
    class EmpLinkList(object):
        def __init__(self):
            self.__head = None
    
        # 添加雇员到链表
        def add(self, emp):
            # 假定,当添加雇员时,id是自增长,即id的分配总是从小到大
            # 因此我们将该雇员直接加入到本链表的最后 即可
            if self.__head is None:
                self.__head = emp
                return  # 注意这个return
            # 如果不是添加第一个雇员,需要建立一个辅助指针,定位到最后
            cur = self.__head
            while cur.next is not None:
                cur = cur.next
            cur.next = emp
    
        def travel(self, no):
            if self.__head is None:
                print("第 %d 链表为空" % (no + 1))
                return
            print("第 %d 链表信息为:" % (no + 1))
            cur = self.__head
            while cur is not None:
                print('=>id = %d name = %s' % (cur.emp_id, cur.emp_name))
                cur = cur.next
            print()
    
        def find_emp_info(self, went_id):  # 如果找到,就返回emp,没找到就返回None
            if self.__head is None:
                print("链表为空")
                return None
            cur = self.__head
            while cur is not None:
                if cur.emp_id == went_id:
                    return cur  # 这时cur就指向要查找的雇员
                cur = cur.next
    
    
    if __name__ == '__main__':
        hashtable = HashTable(7)  # 创建哈希表
        while True:
            for no, item in enumerate(hashtable.menu):
                print("%d : %s 功能" % (no + 1, item))
            active_no = int(input("请输入你要执行的功能:"))
            active = getattr(hashtable, hashtable.menu[active_no - 1])
            if active_no == 1:
                emp_id = int(input("请输入员工id:"))
                emp_name = input("请输入员工姓名:")
                emp_obj = Employee(emp_id, emp_name)
                active(emp_obj)
            elif active_no == 3:
                emp_id = int(input("请输入要查找的员工id:"))
                active(emp_id)
            else:
                active()
    

    在这里插入图片描述

    • 可以再扩展“删除”雇员的功能,我们只需要现在 EmpLinkList中写出单链表删除的方法,然后再到HashTable中添加一个删除的方法,就行了
    展开全文
  • 哈希表数据结构实现代码,符合ADT要求,头文件放ADT函数接口定义和存储结构定义,cpp文件放实现,在控制台查看输出,C语言实现,功能多,注释多,轻松易懂,可用来初学或者作业完成
  • 哈希表 这是哈希表数据结构的简单实现
  • 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());




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

    1. 哈希表(Hash table)

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

    个人理解:与列表不同的是,哈希表的索引是Key,直接通过Key值访问value,而不同于列表,通过整数[0,∞)[0,infty)[0,∞)作为索引存储值。

    使用哈希表可以进行非常快速的查找操作,查找时间为常数,同时不需要元素排列有序;python的内建数据类型:字典,就是用哈希表实现的。

    python中的这些东西都是哈希原理:字典(dictionary)、集合(set)、计数器(counter)、默认字典Defaut dict)、有序字典(Order dict).

    2. Python中的应用

    字典

    Python中的字典便应用了哈希表的原理,能使关键字和值一一对应。

    字典的初始化:

    a = dict()
    b = {}
    c = {'a': 1, 'b': 2, 'b': '3'}  # 冒号左边是key,右边是value,由于存在重复的b,最后剩下右边的'b':3

    访问字典中的value

    print "c['a']: ", c['a']

    修改字典

    c['a'] = 0 # 将原来映射的1变为0
    c['c'] = 4 # 添加新的键值对

    删除字典元素

    del c['a'] #删除key为a的键值对
    c.clear #清除字典c中所有的键值对
    del c #直接删除字典c

    Python之哈希表_wycgi的博客-CSDN博客blog.csdn.net
    6046c886525210a34a51fd985db00d5c.png
    展开全文
  • 这是百度上给出的回答:简而言之,为什么要有这种数据结构呢?因为我们想不经过任何比较,一次从表中得到想要搜索的元素。所以就构造出来了哈希表,通过某种函数(哈希函数)使元素的存储位置与它的关键码之间能够建立...
  • 哈希表 数据结构 课程设计 C++ 报告 资源整合 希望支持
  • 哈希表哈希表(Hash table),是存储键值(Key Value)对数据的一种数据结构。例如,我们可以将人的名字作为键,性别作为值来存储。通过把键映射到表中的一个位置来访问数据,以提高查找速度。而这个映射关系就是哈希...
  • 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。 [测试数据] 取读者周围较熟悉的30个人名
  • 需要插入到哈希表里的数据在第一次被哈希化的时候,保证是除以质数,这个是可以避免同余数。之后再哈希化。 否则会出现步长为0的情况,或者总是相同的情况。 这样的理解是是否正确,但是为什么再往上的解释上出现...
  • 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • "======初始化哈希表=====\n" ) ; init ( & hashTable ) ; printf ( "======插入=====\n" ) ; if ( insert ( & hashTable , 1 ) ) { printf ( "插入成功\n" ) ; } else { printf ( "插入失败\...
  • 含需求分析、概要设计、详细设计、调试分析、使用说明、测试结果、附件。...待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。
  • 1、讲解和演示哈希表的建立和数据查询功能的实现原理; 2、讲解和演示哈希表用于映射类(CMap)的开发方法;
  • 点击蓝字关注我们AI研习图书馆,发现不一样的精彩世界数据结构常见数据结构概述搞定求职笔试or面试,不要着急刷题,先弄懂什么是数据结构~~1976 年,一个瑞士计算机科学家写了一本书:《Algorithms + Data ...
  • ---------------------------------------- android培训、java培训、...本文主要探讨一下HashMap & HashSet & Hashtable 等集合的哈希表数据结构 了解hash()方法 与equals() 方法的关联,说一下本人的理解 "哈希表
  • 哈希表数据结构

    2018-06-29 13:57:45
    哈希表数据结构哈希表数据结构哈希表数据结构哈希表数据结构
  • 数据结构 Hash表(哈希表

    万次阅读 多人点赞 2018-05-20 01:23:34
    参考链接:数据结构(严蔚敏) 什么是Hash表 要想知道什么是哈希表,那得先了解哈希函数 哈希函数 对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树,它们的查找都是先从根节点进行查找,从节点取出...
  • Redis 数据结构哈希表 超实战追 - 女生技术 抠: .x. Redis 的字典底层使用哈希表实现说到哈希表大家应该能联想到 HashMap 或者是 Hashtable 也应该能联想到 key value 的存储形式 以及哈希表扩容哈希算法等知识点...
  • JAVA中的哈希表 / 散列表数据...哈希表数据结构: 哈希表是一个数组和单向链表的结合体 哈希表结合了数组和单向链表的优点,查询效率和增删效率都很高 哈希表:一维数组,数组中的每一个元素都是一个单向链表 ...
  • 数据结构哈希表An Hash Table is a hash implementation of a hash table data structure. Instead of using a custom key to store the value in a map, the data structure performs a hashing function on the ...
  • 福 建 工 程 学 院 课 程 设 计 课程 题目 专业 班级 座号 姓名 算法与数据结构 哈希表 网络工程 xxxxxx 班 xxxxxxxxxxxx xxxxxxx 2011 年 12 月 31 日 实验题目哈希表 一 要解决的问题 针对同班同学信息设计一个...
  • 数据结构哈希表

    2014-12-16 21:04:48
    数据结构中的哈希表详细解析,有力与对数据结构的理解,更有利于对哈希表的理解,其中的是C语言
  • 数据结构哈希表-源码

    2021-02-12 04:52:56
    数据结构哈希表
  • 数据结构(C语言版)实习,哈希表,取余,二次散列法解决冲突

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,655
精华内容 7,462
关键字:

哈希表数据结构

数据结构 订阅