首页 / 算法 / 【算法导论】简单哈希表的除法实现
【算法导论】简单哈希表的除法实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【算法导论】简单哈希表的除法实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3326字,纯文字阅读大概需要5分钟。
内容图文
哈希表,又名散列表,hashtable。。。云云,看似很高大上,其实不过是直接寻址的延伸而已。直接寻址为何物,看一个数组:a[10],那么取其中一个元素a[1],这就是直接寻址,直接去这个a+1的地址上,就找到了这个数值,时间复杂度为O(1)。而哈希表的目的就是要让查找的时间复杂度尽量往O(1)上靠。
一、哈希表的最简单形式
假如有10000个数,比如0~9999,是可能出现的数字的集合,我们现在要将一段时间内,出现的数字,全部保存起来。如果出现的数字都不重复的情况下,我们可以使用一个长度为10000的数组a[10000]来保存,如果数字987出现了,那么我们直接将其保存在a[987]元素上,以此类推。当我们要查询某个数是否出现的时候,比如1002这个数,是否出现,我们可以直接去找a[1002],看看值是否是1002,为了保险起见,也可以在初始化的时候将数组做-1初始化。这样,查找的时间复杂度就是O(1)。
二、改进的哈希表
上面的做法感觉是很快,但是却有问题,太浪费空间了。还是上面的例子,假如可能出现的集合为0~9999这一万个数,但是我们可以预知,实际会出现的数字只有最多10个。如果按照上面的做法,就需要为查找这10个数,而花费10000个空间?是不是太奢侈了点?
其次,上面的做法,基础在于所有出现的数组,都不重复,如果我们人品太好,总共出现两个888怎么办?我们又想知道,888出现了几次?显然这时候,一个a[888]空间是不够的。
为了解决上面两个问题,分两步来做:
1、压缩存储空间。
如何压缩?这里要用到通常所说的哈希函数,哈希函数的作用,就是将大的集合数据,印射到一个相对较小的,我们能够接受的集合范围内,使得速度和内存空间达到一个平衡。比如这里,0~9999一万个可能出现的数字集合,而最多实际只会出现10个。我们就可以使用a%b(取余)操作来处理,比如这里,我们可以使用a%10,来让所有出现的数据的范围由0~9999,变成0~9这十个数,然后就可以使用一个a[10]的数组,去搞定直接寻址。
2、使用链表解决重复出现数据的问题
像上面说的,出现两个888怎么搞?那么我们在a[888]这个位置上,不放元素,我们将a数组作为一个链表数组,a[888]放链表的位置,这样,出现两个888,每次都从链表的头部插入,这样就能放的下了。
如果查找的时候,时间复杂度就不能是单单的O(1)了。我们考虑最坏的情况,比如n个元素的集合,数组的长度为m,当然(n>m)。这时候,除却哈希函数的取余操作的O(1),还要加上(n/m)的链表长度的查找,这是在所有位置链表的长度都相同的情况。如果链表的情况很极端。。。这就不好了。。
所以根据上面的分析,不难发现,这个哈希函数(散列函数)很关键,最好是能让数据,平均的分布到各个位置的链表上,而不要集中到一个或某几个,因为这样会造成某一个链表的长度很长,那么查询起来,时间复杂度就不理想了。
关于散列函数(哈希函数)的取法,有很多种,这里就不再讨论,下面给出除法(取余法)的散列函数,实现简单的哈希表代码:
#include <iostream> using namespace std; /** * @作者:Alex/苦咖啡 * @时间:2015.03.18 * @博客:http://blog.csdn.net/cyp331203 */ struct node { int key; node* next; node* pre; }; struct List { node* head; List() : head(NULL) { } ~List() { node* tmp = NULL; while (head != NULL) { tmp = head->next; delete head; head = tmp; } } void print() { node* tmp = head; while (tmp != NULL) { cout << tmp->key << ' '; tmp = tmp->next; } cout << endl; } void insertHead(int key) { if (head != NULL) { node* n = new node(); n->key = key; n->next = head; head->pre = n; head = n; } else { head = new node(); head->key = 5; } } node* search(int key) { node* pre = NULL; node* curr = head; while (curr != NULL && curr->key != key) { pre = curr; curr = curr->next; } if (curr == NULL) { return NULL; } else if (pre == NULL) { return this->head; } else { return pre->next; } } void deleteNode(node* n) { if (n != NULL) { n->pre->next = n->next; n->next->pre = n->pre; delete n; } } }; //void deleteList(List* l) { // if (l != NULL && (l->head) != NULL) { // node* pre = NULL; // node* curr = l->head; // while (curr != NULL) { // pre = curr; // delete curr; // curr = pre->next; // } // } //} struct HashTable { List* arr; HashTable() { arr = new List[100]; } //析构 ~HashTable() { for (int i = 0; i < 100; i++) { if (arr + i != NULL) { // deleteList(arr + i); delete (arr+i); } } } void CHAINED_HASH_INSERT(int key) { (arr + (key % 100))->insertHead(key); } node* CHAINED_HASH_SEARCH(int key) { return (arr + (key % 100))->search(key); } void CHAINED_HASH_DELETE(node* n) { if (n != NULL) { (arr + (n->key % 100))->deleteNode(n); } } }; int main() { HashTable* ht = new HashTable(); ht->CHAINED_HASH_INSERT(5); node* n = ht->CHAINED_HASH_SEARCH(5); // cout << n->key << endl; ht->CHAINED_HASH_INSERT(205); // n.print(); ht->arr[5].print(); return 0; }
原文:http://blog.csdn.net/cyp331203/article/details/44424983
内容总结
以上是互联网集市为您收集整理的【算法导论】简单哈希表的除法实现全部内容,希望文章能够帮你解决【算法导论】简单哈希表的除法实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。