精华内容
下载资源
问答
  • 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中添加一个删除的方法,就行了
    展开全文
  • python实现哈希表

    千次阅读 2019-09-06 22:35:26
    # python 实现哈希表 class HashTable: """ 哈希函数的构造 解决冲突 """ def __init__(self, source): self.source = source self._index = [] self._val = [] self.table =...
    # python 实现哈希表
    
    class HashTable:
        """
        哈希函数的构造
        解决冲突
        """
    
        def __init__(self, source):
            self.source = source
            self._index = []
            self._val = []
            self.table = []
            self._mod = 13
    
        def Output(self):
            print(self._index)
            print(self._val)
        
        def _create_table(self):
            """
            初始化哈希表
            哈希表长度最短为取余因子_mod,一般为源数据长度
            """
            if len(self.source) < self._mod:
                length = self._mod
            else:
                length = len(self.source)
            
            self._index = [i for i in range(length)]
            self._val = [None for i in range(length)]
    
        def _func_hash(self):
            """
            构建哈希函数
            """
            for sour in self.source:
                remainder = sour % self._mod
                if self._val[remainder] is None:
                    self._val[remainder] = sour
                else:
                    # 处理冲突
                    rem = remainder
                    while self._val[rem] is not None:
                        if(rem + 1 >= len(self._val)):
                            rem = -1
                        rem += 1
                    self._val[rem] = sour
            self.table = list(zip(self._index, self._val))
    
    
        def get(self, num):
            """
            查找
            """
            rem = num % self._mod
            if self._val[rem] != num:
                while True:
                    if(rem + 1 >= len(self._val)):
                        rem = 0
                    if self._val[rem] == num:
                        break
                    rem += 1
            return rem
        
        def run(self):
            self._create_table()
            self._func_hash()
            self.Output()
    
    if __name__ == '__main__':
        test = [12, 15, 17, 21, 22, 25, 13, 0]
        h = HashTable(test)
        h.run()
        h.get(12)
    
    

    只是为了巩固哈希表实现的原理,代码本身没什么用

    展开全文
  • 主要介绍了使用python实现哈希表、字典、集合操作,本文通过实例代码给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下
  • Leetcode[1][202] python实现 哈希表Leetcode (1) 两数之和题目分析代码学习心得Leetcode (202) 快乐数题目分析代码学习心得 Leetcode (1) 两数之和 题目 给定一个整数数组 [nums] 和一个目标值 target,请你在该...

    Leetcode (1) 两数之和

    题目

    给定一个整数数组 [nums] 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

    给定 nums = [2, 7, 11, 15], target = 9
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

    分析

    法一:
    利用python中的字典(dict)来构建hashtable,与此前数构课程使用的C++有所不同。
    初始化一个字典后,利用enumerate()将给定的nums[ ] 使得列表中的每个元素 v 有与之顺序对应的 i ,将其全部存入字典中,其中 i 为value, v 为key。
    遍历字典,找到与当前循环的key相加等于target的数,返回对应的[i1, i2]。

    法2:
    只进行了1次循环。与法1区别在于构建哈希表时并不是直接存入对应的 iv ,而是存入 target-v 和相对应的 i ,同时边构建边判断 v 是否已在字典中,若已在,则可直接返回结果。

    代码

    class Solution:
        def twoSum1(self, nums, target): #48ms
            hashtable = {}
            for i,v in enumerate(nums):
                hashtable[v] = i
            for i2,v2 in enumerate(nums):
                if target-v2 in hashtable and i2 != hashtable[target-v2]:
                    return [i2, hashtable[target - v2]]
                    
    
        def twoSum2(self, nums, target): #56ms
            hashtable = {}
            for i,v in enumerate(nums):
                if v in hashtable:
                    return[hashtable[v],i]
                else:
                    hashtable[target - v] = i
                    
    

    学习心得

    熟悉了字典的使用,学会了使用py中的dict和enumerate()来构建哈希表。

    Leetcode (202) 快乐数

    题目

    编写一个算法来判断一个数是不是“快乐数”。 一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。

    输入: 19
    输出: true
    解释:
    12 + 92 = 82
    82 + 22 = 68
    62 + 82 = 100
    12 + 02 + 02 = 1

    分析

    实际上非快乐数始终为一个循环:4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4。
    首先,初始化一个py中的集合set,通过一个循环:将该数进行快乐计算:借用map函数分割然后计算平方和,赋值给n,若所得到n不在已有的set中,则将该数加入set并再次循环。
    若该数不是快乐数,则循环一轮后遇到自己,输出。
    若该数是快乐数,会得到1,当遇到两次1时,输出。
    最后判断输出的数是否为1。

    代码

    class Solution:
        def isHappy(self, n): # 60ms
            a = set()
            while n not in a:
                a.add(n)
                n = sum(map(lambda x: x**2, map(int, str(n))))
            return n == 1
    

    学习心得

    set(): 创建一个无序不重复元素集
    a.add(x):给集合a添加元素 x
    学习了map()函数的使用,包括使用lambda匿名函数进行“快乐计算”,以及给列表中的元素进行类型转换。

    展开全文
  • python实现哈希表

    2014-01-30 12:53:00
    哈哈,这是我第一篇博客园的博客。尝试了一下用python实现的哈希表,首先处理冲突的方法是开放地址法,冲突表达式为Hi=(H(key)+... 3 #实现哈希表(线性地址再散列) 4 5 def ChangeKey(key, m, di): 6 ke...

    哈哈,这是我第一篇博客园的博客。尝试了一下用python实现的哈希表,首先处理冲突的方法是开放地址法,冲突表达式为Hi=(H(key)+1)mod m,m为表长。

     1 #! /usr/bin/env python
     2 #coding=utf-8
     3 #实现哈希表(线性地址再散列)
     4 
     5 def ChangeKey(key, m, di):
     6     key01 = (key+di) % m
     7     return key01
     8 
     9 a = raw_input("Please entry the numbers:\n").split()
    10 m = len(a)
    11 dict01 = {}
    12 for i in a:
    13     key = int(i) % m
    14     if "%s" % key in dict01:
    15         NewKey = ChangeKey(key, m, 1)
    16         while "%s" % NewKey in dict01:         #因为下面的dict01的key值是以字符串来保存,因此这里作判断时也要用字符串格式
    17             NewKey = ChangeKey(NewKey, m, 1)
    18         dict01["%s" % NewKey] = int(i)
    19     else:
    20         dict01["%s" % key] = int(i)
    21 print dict01

     

    接下来是用开放地址法。

    目标,输入:key/value列表,输出:运用拉链法的哈希表

    对于下面的这个函数,输入的是一个这样的列表数据结构:["key01 val01", "key02 val01", "key03 val01", "key01 val02", "key02 val02", "key01 val03", ...]

    而函数返回一个这样的字典数据结构:{key01:[val01, val02, val03, ...],key02:[val01, val02...], key03:[val01, ...]}。这个函数和MapReduce思想中的Reduce功能是类似的。

    代码如下:

    def chainHash(InputList):
        res = {}
        for line in InputList:
            if line.split()[0] not in res:
                temp = []        #因为在拉链法中,键值包含多个对象,因此需要新建一个列表,把键值保存在这个列表中
                temp.append(line.split()[1])
                res["%s" % line.split()[0]] = temp
            else:
                res["%s" % line.split()[0]].append(line.split()[1])
        return res

     

    转载于:https://www.cnblogs.com/cjyfff/p/3536525.html

    展开全文
  • 10.python实现哈希表

    2020-08-31 11:21:14
    哈希表 通过最简单的取模运算作为哈希算法 class HashNode(object): def __init__(self, id, data): self.id = id self.data = data self.next = None def __str__(self): return '(%d,%s)' % (self.id, str...
  • 哈希表 哈希表(Hash Table, 又称为散列表),是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。哈希函数h(k)将元素关键字k作为自变量,返回元素的存储下标。 简单哈希函数: 除法哈希:h(k) ...
  • 对于两个C++语言的源程序代码,用哈希表的方法分别统计两个程序中使用C++语言关键字的情况,并最终按定量的计算结果,得出两份程序的相似性。 二、需求分析 建立C++语言关键字的哈希表,统计在每个源程序中C++关键字...
  • python哈希表就是字典啊,还怎么实现呢? 存储10位同学,每位同学有姓名、籍贯和成绩 直接实现哇,好像也没啥可以写的 stu = {'z1': ('sx', 96), 'z2': ('sd', 97), 'z3': ('sx', 97),} stu.update({'z4': ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 647
精华内容 258
关键字:

python实现哈希表

python 订阅