python中的哈希表数据结构-阿里云开发者社区

开发者社区> python之战> 正文

python中的哈希表数据结构

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

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

python中的dict类型就是哈希表的原理,存储方式是key-value,通过键来快速的访问value,字典在访问操作上时间复杂度为O(1)。

用python实现一个简单的哈希表:key为纯数字作为索引,使用线性表存储

class HashTable:
    def __init__(self, size):
        self.elem = [None for i in range(size)]  # 使用list数据结构作为哈希表元素保存方法
        self.count = size  # 最大表长

    def hash(self, key):
        return key % self.count  # 散列函数采用除留余数法

    def insert_hash(self, key, value):
        """插入关键字到哈希表内"""
        address = self.hash(key)  # 求散列地址
        while self.elem[address]:  # 当前位置已经有数据了,发生冲突。
            address = (address + 1) % self.count  # 线性探测下一地址是否可用
        self.elem[address] = value  # 没有冲突则直接保存。

    def search_hash(self, key):
        """查找关键字,返回布尔值"""
        star = address = self.hash(key)
        while self.elem[address] != key:
            address = (address + 1) % self.count
            if not self.elem[address] or address == star:  # 说明没找到或者循环到了开始的位置
                return False
        return True

若关键字为k,则其值存放在f(k)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数,按这个思想建立的表为散列表。

对不同的关键字可能得到同一散列地址,即k1≠k2,而f(k1)=f(k2),这种现象称为冲突(英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。

若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Python数据结构
说实话,数据结构是一门很难的课程,我也没有系统的学过,如果有兴趣的同学可以去看看数据结构的书籍,以后可以和我讨论一下,在这里说说我自己的理解吧。 数据结构就是数据以什么样的形式存储;而以什么样的形式存储就得用相应的方法去处理分析数据(这是最近看数据分析的一点小体会),今天不过多的展开,介绍4个python的内置数据结构,分别是列表(list),字典(dict),元组(tuple),集合(set)。
599 0
oracle、mysql、sybase和sqlserver复制表结构和数据
Sql Server(sybase): 1.复制表结构: 新建表student2,并且结构同表syn_xj_student一致。Sql语句如下: select * into syn_xj_student2 from syn_xj_student where 1=2 2.复制表数据,并...
682 0
linux内核数据结构之链表【转】
转自:http://www.cnblogs.com/Anker/archive/2013/12/15/3475643.html 1、前言    最近写代码需用到链表结构,正好公共库有关于链表的。
730 0
从一个集合中查找最大最小的N个元素——Python heapq 堆数据结构
Top N问题在搜索引擎、推荐系统领域应用很广, 如果用我们较为常见的语言,如C、C++、Java等,代码量至少也得五行,但是用Python的话,只用一个函数就能搞定,只需引入heapq(堆队列)这个数据结构即可。
1113 0
python实现单向循环链表数据结构及其方法
首先要说明一下研究数据结构有什么用,可能就像高数之类的在生活中并没有多少用处,但是离不开他,很多大公司面试也会问这个东西;但是要落实到某一个具体的业务场景,我也不知道,但并不代表这些东西没用,也可能是这些模型只是为了让我们能理解更多有用的东西。
1189 0
+关注
python之战
专注python学习与应用擅长爬虫、web、全栈,专注RPA技术实施;(个人公号:Python之战)
90
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载