数据结构_哈希表_python实现

定义: 哈希表是一种数据结构,它是指一种由数组存储链表头部的表。我们根据哈希函数来对数据进行映射,从而把数据分配到这个表的不同链表中。这么做的目的是因为,单个链表进行查找效率很低,你只能逐一查找。而通过哈希函数分配到不同链表后,你只需要再从那个比较小的链表中进行查找。能够大大的提高查找效率。因此,判断哈希函数的好坏主要看能否把数据均匀分配到不同链表中,尽量不能出现大量数据聚集到同一链表的情况。

示意图
在这里插入图片描述

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

具体问题:
google公司的一个上机题:

有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,名字,住址…),当输入该员工的id时,要求查找到该员工的 所有信息.

要求:

  1. 不使用数据库,速度越快越好=>哈希表(散列)
  2. 添加时,保证按照id从低到高插入 [思考:如果id不是从低到高插入,但要求各条链表仍是从低到高,怎么解决?]
  3. 使用链表来实现哈希表, 该链表不带表头

代码实现:

#哈希表保存雇员信息
'''
1、一个数组,里面存储着链表,链表存储雇员信息
2、也就是说数组里面实际存储着链表的头节点
3、定义雇员结构{id,name,address},即链表的结点
4、链表[]
5、HashTab[]
6、散列函数
'''

class Emp(object):
    def __init__(self,ID,name):
        self.ID = ID
        self.name=name
        self.next=None
    def show(self):
        print('雇员信息:'+str(self.ID)+' '+self.name)
        
class LinkedList(object):
    def __init__(self):
        self.head=None
    
    #添加雇员
    def add(self,emp):
        if self.head==None:
            self.head=emp
            return
        curEmp = self.head
        while True:
            if curEmp.next==None:
                break
            curEmp=curEmp.next
        curEmp.next=emp
    
    #寻找雇员,找到后返回emp,否则返回None
    def finEmp(self,ID):
        if self.head == None:
            return None
        curEmp = self.head
        while(True):
            if curEmp.ID == ID:
                break
            if curEmp.next == None:
                curEmp=None
                break
            curEmp = curEmp.next
        return curEmp
    
    #显示雇员
    def showlist(self,no):
        if self.head==None:
            print("链表{}为空!".format(no))
            return
        print('链表{}的信息为:'.format(no))
        curEmp = self.head
        while True:
            print('=> id={} name={} '.format(curEmp.ID,curEmp.name))
            if curEmp.next==None:
                break
            curEmp = curEmp.next#后移遍历
            
class HashTab(object):
    
    def __init__(self,size):
        self.arr = [LinkedList() for i in range(size)]
        self.size = size
     
    def hashFun(self,ID):
        return ID % self.size
    
    def add(self,emp):
        #根据雇员的id进行哈希,进而分配到不同的链表
        arrNo = self.hashFun(emp.ID)
        #将emp添加到对应的链表中
        self.arr[arrNo].add(emp)
    
    def lookAll(self):
        for i in range(self.size):
            self.arr[i].showlist(i+1)
    
    #根据输入遍历hashTab
    def findEmp(self,ID):
        empNo = self.hashFun(ID)
        emp = self.arr[empNo].finEmp(ID)
        if emp!=None:
            print('在第{}条链表中找到该雇员 name = {}'.format(empNo+1,emp.name))
            return emp
        else:
            print('在哈希表中没有找到该成员~')
        
            
    
        
emp1 = Emp(11,'肖茵')
emp2= Emp(672,'刘伟')
emp3= Emp(23,'王五')
emp4= Emp(42,'李四')
emp5= Emp(45,'张三')

haxi = HashTab(3)

while(True):
    print()
    key = input('add:添加雇员\nfind:查找雇员\nlist:显示雇员\nexit:退出系统\n')
    if key=='add':
        ID = int(input('ID = '))
        name = input('name = ')
        emp = Emp(ID,name)
        haxi.add(emp)
    elif key=='list':
        haxi.lookAll()
    elif key=='find':
        ID = int(input("ID = "))
        haxi.findEmp(ID)
    elif key=='exit':
        print('退出成功')
        break
    



版权声明:本文为qq_44273739原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_44273739/article/details/105416433

智能推荐

Qcon演讲纪实:详解如何在实时视频通话中实现AR功能

2018年4月20日-22日,由 infoQ 主办的 Qcon 2018全球软件开发大会在北京如期举行。声网首席 iOS 研发工程师,iOS 端移动应用产品设计和技术架构负责人龚宇华,受邀分享了《基于 ARkit 和 ARcore,在实时视频通话中实现 AR 功能》,在演讲中剖析了 AR 与 VR 差异,ARKit 的工作原理,以及逐步讲解如何基于 ARKit 与声网Agora SDK 创建 AR...

POJ2348 UVa10368 HDU1525 Euclid's Game【博弈】

Euclid's GameTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4106    Accepted Submission(s): 1947 Probl...

使用Breeze.js编写更好的查询

这篇文章是由同行评审Agbonghama柯林斯 。 感谢所有SitePoint的审稿作出SitePoint内容也可以是最好的! 数据量正在迅速发展,他们正在变得越来越复杂,维护。 许多开发人员希望避免由数据问题他们的工作过程中造成的问题和头痛。 一个使我们的工作更轻松的图书馆是Breeze.js 。 在这篇文章中,我们将讨论我们如何能够写出更好的查询与Breeze.js。 但是首先,我们应该知道什...

Netty框架构建Nio编程

~~~ 随手点赞,养成习惯 ~~~ 为什么选择Netty框架 Netty是业界最流行的NIO框架之一,它的健壮性、功能、性能、可定制性和可扩展性在同类框架中都是首屈一指的。 优点: ① API使用简单,开发门槛低 ②功能强大,预置了多种编解码功能,支持多种主流协议 ③ 定制能力强,可以通过ChannelHandler对通信框架进行灵活地扩展; ④性能高,通过与其他业界主流的NIO框架对比,Nett...

【JZOJ5262】【GDOI2018模拟8.12】树(DP,性质题)

Description Solution 首先我们可以知道两个性质:1、路径u-v和路径v-w可以合并为路径u-w;2、路径u1-v1加路径u2-v2和路径u1-v2加路径u2-v1是等价的(就是起始点和终点可以互换) 那么知道这些性质之后就很好做了。我们只用知道每个点多少次做起点和多少次做终点。 我们设f[i]表示满足i子树的需求i上的值要是多少。 那么枚举i的所有儿子,判断a[i]-f[i],...

猜你喜欢

【String-easy】541. Reverse String II 反转的元素,有反转个数和间隔

1. 题目原址 https://leetcode.com/problems/reverse-string-ii/ 2. 题目描述 3. 题目大意 给定一个字符串,和字符串的间隔k, 这个k表示每k个数反转一次,然后再间隔k个元素再反转k个元素。 4. 解题思路 只要按照间隔去反转就可以了。然后间隔k个元素不反转是通过让i每次递增 2*k完成的。 5. AC代码 6. 相似题型 【1】344. Re...

【C语言笔记结构体】

我们都知道C语言中变量的类型决定了变量存储占用的空间。当我们要使用一个变量保存年龄时可以将其声明为int类型,当我们要使用一个变量保存某一科目的考试成绩时可以将其声明为float。 那么,当我们要做一个学生信息管理系统时,需要保存学生的姓名、学号、年龄等信息,该怎么做呢? 如当要保存三个学生的信息时, 方法一是: 方法二是: 显然,方法二跟更清晰,因为它把name、num、age都集成在一个模板,...

39. Combination Sum 回溯算法简析

LeetCode传送门     这道题要求给你一组正数 C,然后给你一个目标数 T,让你从那组C中找到加在一起等于 T 的那些组合。     例如:给你 [2,3,6,7] 和 7,则返回 [[2,2,3],[7] ] 。      想解决这个问题前,我们首先引入一个新问题,图(树)的遍历问题。  ...

git安装|Linux系统安装 git|Linux如何安装git?Linux通过远程安装git|

Git是一个开源的分布式版本控制系统,可以有效、高速地处理项目版本管理。Git 是 Linus Torvalds 为了帮助管理 Linux 内核开发而开发的一个开放源码的版本控制软件。 开发者需要一个GIT账号,通过这个查看项目的提交记录,可以更加清楚项目的开发情况,便于版本控制。 以下介绍在CentOS8操作系统搭建GIT服务器。   一、安装GIT服务器流程   安装GIT...