python-dict和set

Python - dict和set

前言：我们经常会听见很多的概念，哈希值，哈希表，可哈希对象，不可哈希对象，散列表，字典，映射，等等，那么这么多的概念后面到底又有什么区别和联系，它们的本质又是怎么样的，本此系列文章将针对这些概念进行说明，鉴于篇幅较多，本次系列文章将分为两篇来说明，此为第一篇，介绍数据结构哈希表与哈希值。

一、可哈希对象与不可哈希对象

1.1 哈希表（散列表）——hash table

哈希表，又称之为散列表，是一种空间换时间的存储结构，是在算法中提升效率的一种比较常用的方式，但是所需空间太大也会让人头疼，所以通常需要在二者之间权衡。我们会在之后的具体算法章节中得到更多的领悟。

哈希表（散列表），是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。也就是说，把关键字映射到一个表中的位置来直接访问记录，以加快访问速度。

• 关键字，也称之为键，或者是Key，这就是我们哈希函数计算的依据
• 记录，也称之为值，，也称之为哈希值，或者是Value，也就是我们通过key然后经过哈希函数运算之后得到的结果，存储这个记录，即存放哈希函数得到的结果的数组称之为 哈希表 或者是 散列表

1.2 哈希表的问题——碰撞Clollision

其中有个特殊情况，就是通过不同的 Key，可能访问到同一个地址，这种现象叫作碰撞（Collision）。

如果“键-值对”在加入哈希表的时候产生了冲突，就必须找另外一个地方来存放它，冲突太多会降低数据插入和搜索的效率，因此希望能找到一个不容易产生冲突的函数，即构造一个地址分布比较均匀的哈希函数。

一个好的散列表设计，除了需要选择一个性能较好的哈希函数，否则冲突是无法避免的，所以通常还需要有一个好的冲突处理方式，目前，这个哈希函数比较常用的实现方法比较多，通常需要考虑几个因素：关键字的长度、哈希表的大小、关键字的分布情况、记录的查找频率，等等。常见的一些哈希函数有：

• 直接寻址法
• 数字分析法
• 平方取中法
• 取随机数法
• 除留取余法

当出现冲突的时候，处理冲突的一些方法有：

• 开放地址法（也叫开放寻址法）
• 再哈希法
• 链地址法
• 建立一个公共溢出区

1.3 什么是可哈希(hashable)？

不可变的数据结构(数字类型（int，float，bool）、字符串str、元组tuple、自定义类的对象)。

不可哈希的数据类型，即可变的数据结构 (字典dict，列表list，集合set)

An object is hashable if it has a hash value which never changes during its lifetime (it needs a hash() method), and can be compared to other objects (it needs an eq()or cmp() method). Hashable objects which compare equal must have the same hash value.

如果一个对象是可哈希的,那么在它的生存期内必须不可变(而且该对象需要一个哈希函数),而且可以和其他对象比较(需要比较方法).比较值相同的对象一定有相同的哈希值，即一个对象必须要包含有以下几个魔术方法：

• __eq__():用于比较两个对象是否相等
• __ cmp__() : 用于比较两个对象的大小关系，它与__eq__只要有一个就可以了
• __hash__()：实际上就是哈希函数（散列函数），返回经过运算得到的哈希值

二、dict

CPython 的字典实现为可调整大小的哈希表。与 B-树相比，这在大多数情况下为查找（目前最常见的操作）提供了更好的性能，并且实现更简单。