解决哈希冲突的几种方法

一、什么是哈希（哈希算法）

  哈希算法是将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。

二、产生哈希冲突的原因

  Hash算法并不完美，有可能两个不同的原始值在经过哈希运算后得到同样的结果， 这样就是哈希碰撞

三、解决哈希冲突的方法

1、开放寻址法（Python字典实现方式）

  这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
Hi=（H（key）+di）% m i=1，2，…，n

Python3.7后字典实现有序

旧有实现结构： 使用一个二维数组，记录hash值，key值的内存地址、value值的内存地址:

新结构：由 Indices(索引，数组实现) 和 Entries(实体，PyDictObject类型) 两种结构组成

indices， 记录字典元素存放的标志位

Entries

2、链式地址法（HashMap实现）

  基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。