如何用dw做网站地图,企业网站上海熙,wordpress屏蔽蜘蛛爬虫,代注册公司需要多少费用哈希表和哈希函数在记录的存储位置和它的关键字之间是建立一个确定的对应关系#xff08;映射函数#xff09;#xff0c;使每个关键字和一个存储位置能唯一对应。这个映射函数称为哈希函数#xff0c;根据这个原则建立的表称为哈希表(Hash Table)#xff0c;也叫散列表。… 哈希表和哈希函数在记录的存储位置和它的关键字之间是建立一个确定的对应关系映射函数使每个关键字和一个存储位置能唯一对应。这个映射函数称为哈希函数根据这个原则建立的表称为哈希表(Hash Table)也叫散列表。以上描述如果通过数学形式来描述就是若查找关键字为 key则其值存放在 f(key) 的存储位置上。由此不需比较便可直接取得所查记录。注哈希查找与线性表查找和树表查找最大的区别在于不用数值比较。冲突若 key1 ≠ key2 而 f(key1) f(key2)这种情况称为冲突(Collision)。根据哈希函数f(key)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集区间上并以关键字在地址集中的“像”作为记录在表中的存储位置这一映射过程称为构造哈希表。构造哈希表这个场景就像汽车找停车位如果车位被人占了只能找空的地方停。构造哈希表由以上内容可知哈希查找本身其实不费吹灰之力问题的关键在于如何构造哈希表和处理冲突。常见的构造哈希表的方法有 5 种1直接定址法说白了就是小学时学过的一元一次方程。即 f(key) a * key b。其中a和b 是常数。2数字分析法假设关键字是R进制数如十进制。并且哈希表中可能出现的关键字都是事先知道的则可选取关键字的若干数位组成哈希地址。选取的原则是使得到的哈希地址尽量避免冲突即所选数位上的数字尽可能是随机的。3平方取中法取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况仅取其中的几位为地址不一定合适而一个数平方后的中间几位数和数的每一位都相关 由此得到的哈希地址随机性更大。取的位数由表长决定。4除留余数法取关键字被某个不大于哈希表表长 m 的数 p 除后所得的余数为哈希地址。即 f(key) key % p (p ≤ m)这是一种最简单、最常用的方法它不仅可以对关键字直接取模也可在折叠、平方取中等运算之后取模。注意p的选择很重要如果选的不好容易产生冲突。根据经验一般情况下可以选p为素数。5随机数法选择一个随机函数取关键字的随机函数值为它的哈希地址即 f(key) random(key)。通常在关键字长度不等时采用此法构造哈希函数较为恰当。解决冲突设计合理的哈希函数可以减少冲突但不能完全避免冲突。所以需要有解决冲突的方法常见有两类1开放定址法如果两个数据元素的哈希值相同则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素程序就会继续往后查找直到找到一个符合查找要求的数据元素或者遇到一个空的表项。例子若要将一组关键字序列 {1, 9, 25, 11, 12, 35, 17, 29} 存放到哈希表中。采用除留余数法构造哈希表采用开放定址法处理冲突。不妨设选取的p和m为13由 f(key) key % 13 可以得到下表。需要注意的是在上图中有两个关键字的探查次数为 2 其他都是1。这个过程是这样的a. 12 % 13 结果是12而它的前面有个 25 25 % 13 也是12存在冲突。我们使用开放定址法 (12 1) % 13 0没有冲突完成。b. 35 % 13 结果是 9而它的前面有个 99 % 13也是 9存在冲突。我们使用开放定址法 (9 1) % 13 10没有冲突完成。2拉链法将哈希值相同的数据元素存放在一个链表中在查找哈希表的过程中当查找到这个链表时必须采用线性查找方法。在这种方法中哈希表中每个单元存放的不再是记录本身而是相应同义词单链表的头指针。例子如果对开放定址法例子中提到的序列使用拉链法得到的结果如下图所示实现一个哈希表假设要实现一个哈希表要求a. 哈希函数采用除留余数法即 f(key) key % p (p ≤ m)b. 解决冲突采用开放定址法即 f2(key) (f(key)i) % size (p ≤ m)1定义哈希表的数据结构class HashTable { public int key 0; // 关键字 public int data 0; // 数值 public int count 0; // 探查次数}2在哈希表中查找关键字key根据设定的哈希函数计算哈希地址。如果出现地址冲突则按设定的处理冲突的方法寻找下一个地址。如此反复直到不冲突为止查找成功或某个地址为空查找失败。/*** 查找哈希表* 构造哈希表采用除留取余法即f(key) key mod p (p ≤ size)* 解决冲突采用开放定址法即f2(key) (f(key) i) mod p (1 ≤ i ≤ size-1)* ha为哈希表p为模size为哈希表大小key为要查找的关键字*/public int searchHashTable(HashTable[] ha, int p, int size, int key) { int addr key % p; // 采用除留取余法找哈希地址 // 若发生冲突用开放定址法找下一个哈希地址 while (ha[addr].key ! NULLKEY ha[addr].key ! key) { addr (addr 1) % size; } if (ha[addr].key key) { return addr; // 查找成功 } else { return FAILED; // 查找失败 }}3删除关键字为key的记录在采用开放定址法处理冲突的哈希表上执行删除操作只能在被删记录上做删除标记而不能真正删除记录。找到要删除的记录将关键字置为删除标记DELKEY。public int deleteHashTable(HashTable[] ha, int p, int size, int key) { int addr 0; addr searchHashTable(ha, p, size, key); if (FAILED ! addr) { // 找到记录 ha[addr].key DELKEY; // 将该位置的关键字置为DELKEY return SUCCESS; } else { return NULLKEY; // 查找不到记录直接返回NULLKEY }}4插入关键字为key的记录将待插入的关键字key插入哈希表先调用查找算法若在表中找到待插入的关键字则插入失败若在表中找到一个开放地址则将待插入的结点插入到其中则插入成功。 public void insertHashTable(HashTable[] ha, int p, int size, int key) { int i 1; int addr 0; addr key % p; // 通过哈希函数获取哈希地址 if (ha[addr].key NULLKEY || ha[addr].key DELKEY) { // 如果没有冲突直接插入 ha[addr].key key; ha[addr].count 1; } else { // 如果有冲突使用开放定址法处理冲突 do { addr (addr 1) % size; // 寻找下一个哈希地址 i; } while (ha[addr].key ! NULLKEY ha[addr].key ! DELKEY); ha[addr].key key; ha[addr].count i; }}5建立哈希表先将哈希表中各关键字清空使其地址为开放的然后调用插入算法将给定的关键字序列依次插入。public void createHashTable(HashTable[] ha, int[] list, int p, int size) { int i 0; // 将哈希表中的所有关键字清空 for (i 0; i ha.length; i) { ha[i].key NULLKEY; ha[i].count 0; } // 将关键字序列依次插入哈希表中 for (i 0; i list.length; i) { this.insertHashTable(ha, p, size, list[i]); }}完整代码class HashTable { public int key 0; // 关键字 public int data 0; // 数值 public int count 0; // 探查次数} public class HashSearch { private final static int MAXSIZE 20; private final static int NULLKEY 1; private final static int DELKEY 2; private final static int SUCCESS 0; private final static int FAILED 0xFFFFFFFF; /** * 查找哈希表 * 构造哈希表采用除留取余法即f(key) key mod p (p ≤ size) * 解决冲突采用开放定址法即f2(key) (f(key) i) mod p (1 ≤ i ≤ size-1) * ha为哈希表p为模size为哈希表大小key为要查找的关键字 */ public int searchHashTable(HashTable[] ha, int p, int size, int key) { int addr key % p; // 采用除留取余法找哈希地址 // 若发生冲突用开放定址法找下一个哈希地址 while (ha[addr].key ! NULLKEY ha[addr].key ! key) { addr (addr 1) % size; } if (ha[addr].key key) { return addr; // 查找成功 } else { return FAILED; // 查找失败 } } /** * 删除哈希表中关键字为key的记录 * 找到要删除的记录将关键字置为删除标记DELKEY */ public int deleteHashTable(HashTable[] ha, int p, int size, int key) { int addr 0; addr searchHashTable(ha, p, size, key); if (FAILED ! addr) { // 找到记录 ha[addr].key DELKEY; // 将该位置的关键字置为DELKEY return SUCCESS; } else { return NULLKEY; // 查找不到记录直接返回NULLKEY } } /** * 将待插入的关键字key插入哈希表 * 先调用查找算法若在表中找到待插入的关键字则插入失败 * 若在表中找到一个开放地址则将待插入的结点插入到其中则插入成功。 */ public void insertHashTable(HashTable[] ha, int p, int size, int key) { int i 1; int addr 0; addr key % p; // 通过哈希函数获取哈希地址 if (ha[addr].key NULLKEY || ha[addr].key DELKEY) { // 如果没有冲突直接插入 ha[addr].key key; ha[addr].count 1; } else { // 如果有冲突使用开放定址法处理冲突 do { addr (addr 1) % size; // 寻找下一个哈希地址 i; } while (ha[addr].key ! NULLKEY ha[addr].key ! DELKEY); ha[addr].key key; ha[addr].count i; } } /** * 创建哈希表 * 先将哈希表中各关键字清空使其地址为开放的然后调用插入算法将给定的关键字序列依次插入。 */ public void createHashTable(HashTable[] ha, int[] list, int p, int size) { int i 0 // 将哈希表中的所有关键字清空 for (i 0; i ha.length; i) { ha[i].key NULLKEY; ha[i].count 0; } // 将关键字序列依次插入哈希表中 for (i 0; i list.length; i) { this.insertHashTable(ha, p, size, list[i]); } } /** * 输出哈希表 */ public void displayHashTable(HashTable[] ha) { int i 0; System.out.format(pos:\t, pos); for (i 0; i ha.length; i) { System.out.format(%4d, i); } System.out.println(); System.out.format(key:\t); for (i 0; i ha.length; i) { if (ha[i].key ! NULLKEY) { System.out.format(%4d, ha[i].key); } else { System.out.format( ); } } System.out.println(); System.out.format(count:\t); for (i 0; i ha.length; i) { if (0 ! ha[i].count) { System.out.format(%4d, ha[i].count); } else { System.out.format( ); } } System.out.println(); } public static void main(String[] args) { int[] list { 3, 112, 245, 27, 44, 19, 76, 29, 90 }; HashTable[] ha new HashTable[MAXSIZE]; for (int i 0; i ha.length; i) { ha[i] new HashTable(); } HashSearch search new HashSearch(); search.createHashTable(ha, list, 19, MAXSIZE); search.displayHashTable(ha); }}参考资料《数据结构习题与解析》B级第3版转自静默虚空http://www.cnblogs.com/jingmoxukong/p/4332252.html
