php 数据结构 hash表

hash表

定义

  1. hash表定义了一种将字符组成的字符串转换为固定长度(一般是更短长度)的数值或索引值的方法,称为散列法,也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快,这种方法一般用来在数据库中建立索引并进行搜索,同时还用在各种解密算法中
    • 所有可以出现的关键字为u(全集),去重后关键字集合为m(m小于u),散列方法hash就是将u映射到个表t[0,m-1],。这样以u中关键字为自变量,以hash为函数的运算结果就是相应结点的存储地址。从而达到在o(1)时间内就可完成查找。
    • hash函数将u映射为 0-m-1,通常称hash为散列函数(hash function),散列函数hash的作用是压缩待处理的下标范围,使待处理的u个值减少到m个值,从而降低空间开销。
    • t就是散列表(hash table)。
    • hash(key)是关键字key节点的存储地址(亦称散列值或散列地址)。就是通过这个函数得到了数组下标。
    • hash表的核心任然是数组,只是数组的下标是通过hash函数得到的。
    • 比如:有一组数据包括用户名字、电话、住址等,为了快速的检索,我们可以利用名字作为关键码,hash规则就是把名字中每一个字的拼音的第一个字母拿出来,把该字母在26个字母中的顺序值取出来加在一块作为该记录的地址。比如张三,就是z+s=26+19=45。就是把张三存在地址为45处。
  2. hash冲突
    • 两个不同的关键字,由于散列函数值相同,因而被映射到同一表位置上。该现象称为冲突(collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(synonym)。
    • 冲突基本上不可避免的,除非数据很少,我们只能采取措施尽量避免冲突,或者寻找解决冲突的办法。
    • 冲突的频繁程度除了与h相关外,还与表的填满程度相关。
    • 设m和n分别表示表长和表中填入的结点数,则将α=n/m定义为散列表的装填因子(load factor)。α越大,表越满,冲突的机会也越大。通常取α≤1。

hash构造

  1. 散列函数的选择有两条标准:简单和均匀
    • 简单指散列函数的计算简单快速;
    • 匀指对于关键字集合中的任一关键字,散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说,散列函数能将子集k随机均匀地分布在表的地址集{0,1,…,m-1}上,以使冲突最小化。
  2. 常用散列函数
    • 直接定址法:比如在一个0~100岁的年龄统计表,我们就可以把年龄作为地址。
    • 平方取中法:先通过求关键字的平方值扩大相近数的差别,然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关,所以由此产生的散列地址较为均匀
    • 除留余数法:取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数
    • 随机数法:选择一个随机函数,取关键字的随机函数值为它的散列地址

解决hash冲突

  1. 开放定址法:
  2. 拉链法:将所有关键字为同义词的结点链

    链地址法处理冲突时的Hash表

    接在同一个单链表中。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数组t[0..m-1]。凡是散列地址为i的结点,均插入到以t为头指针的单链表中。t中各分量的初值均应为空指针。在拉链法中,装填因子α可以大于1,但一般均取α≤1。

编程应用

  1. Hash表是一个很有用的数据结构,它用O(N)的空间描述一个元素在0到N-1范围内的集合,支持常数级别的添加、删除和查询。遗憾的是,Hash表不能在常数时间内批量删除元素,返回全部元素也需要O(N)的时间,而理论上说这几个操作可以做的更好。

  2. 这个数据结构包含一个整型变量n(表示当前元素个数),以及两个数组members和position,前者用来储存当前集合中的元素,后者是一个长度为N的数组,用来记录每个数在members数组中的什么位置(换句话说members[position[i]] == i总成立)。

    想要查询m是否在当前集合内,只需要看看position[m]是不是在0到n-1的范围 内,并且members[position[m]]是否也确实等于m。添加一个元素只需要把新元素放进members[n++],并更新position的相应数据。删除一个元素只需要把该元素移到members队列末尾(让这个元素和members数组的第n个数对换一下位置),同时更新position的相应数据,然后n减一。清空集合只需要直接令n等于0即可。遍历元素只需要扫描members数组中当前有效的那一段,这显然是O(n)的。变量n就是元素个数,需要查询元素个数时直接返回n就行了。

代码

class HashNode
{
public $key;
public $value;
public $nextNode; public function __construct($key, $value, $nextNode = null)
{
$this->key = $key;
$this->value = $value;
$this->nextNode = $nextNode;
}
}
class HashTable
{
public $table;
public $size = 10; public function __construct($size = 10)
{
$this->table = new SplFixedArray($size);
} private function hashFunction($key)
{
//$key = sprintf("%u",crc32($key));
return $key % $this->size;
} public function insert($key, $value)
{
$index = $this->hashFunction($key);
if (isset($this->table[$index])) {
$node = new HashNode($key, $value, $this->table[$index]);
} else {
$node = new HashNode($key, $value);
}
$this->table[$index] = $node;
} public function find($key)
{
$index = $this->hashFunction($key);
/* @var $current HashNode */
$current = $this->table[$index];
while ($current !== null) {
if ($current->key == $key) {
return $current->value;
} else {
$current = $current->nextNode;
}
}
return null;
}
}
$hashTable =new HashTable();
$hashTable->insert('1',111);
$hashTable->insert('11',222);
$hashTable->insert('111',333);
var_dump($hashTable->find(111));
var_dump($hashTable);
上一篇:数据结构-Hash表


下一篇:【数据结构】Hash表简介及leetcode两数之和python实现