实现哈希表的方法有两种方法:开放寻址法 、链地址法
开放寻址法:在开放寻址法中,所有的元素都存储在哈希表的数组中,冲突发生时会探测下一个可用的位置,直到找到一个空闲的位置。这种方法保持了元素的顺序,但可能导致聚集(clustering)。
链地址法:链地址法使用一个数组来存储指向链表头部的指针,每个链表存储具有相同哈希值的元素。如果发生冲突,新的元素将被添加到该链表的末尾。这种方法可以避免聚集,但不保持元素的顺序。
- #include
- #include
-
- #define SIZE 20
- typedef struct Node {
- int value;
- int key;
- struct Node* next;
- }Node;
-
- typedef struct{
- Node *table[SIZE];
- }HashTable;
-
- //初始化哈希表
- void initHashTable(HashTable *ht){
- for (int i = 0; i < SIZE; i++) {
- ht->table[i] = NULL;
- }
- }
-
- int getKey(int value){
- return value%SIZE;
- }
-
- //向哈希表中插入数据 hash公式就是 value%20
- void addvalue(int value,HashTable *ht){
- Node *node=(Node*)malloc(sizeof(Node));
- node->value=value;
- int key=getKey(value);
- node->key=key;
- node->next=NULL;
- Node *tmp=ht->table[key];
- if(tmp!=NULL){
- while(tmp->next){
- tmp=tmp->next;
- }
- tmp->next=node;
- }else{
- ht->table[key]=node;
- }
- }
-
- //查看哈希表中是否包含此值
- int containValue(int value,HashTable *ht){
- int key=getKey(value);
- if(key<0){
- printf("查询非法数据!");
- return -1;
- }
- Node* tmp=ht->table[key];
- if(tmp==NULL) return 0;
- while(tmp){
- if(tmp->value==value) return 1;
- tmp=tmp->next;
- }
- return 0;
- }
-
- // 释放哈希表内存
- void freeHashTable(HashTable *ht) {
- for (int i = 0; i < SIZE; i++) {
- Node *current = ht->table[i];
- while (current != NULL) {
- Node *temp = current;
- current = current->next;
- free(temp);
- }
- }
- }
-
-
- int main(){
- HashTable table;
- initHashTable(&table);
- addvalue(1,&table);
- addvalue(3,&table);
- addvalue(6,&table);
- addvalue(7,&table);
- addvalue(11,&table);
- addvalue(23,&table);
- addvalue(21,&table);
- addvalue(27,&table);
- addvalue(87,&table);
-
- printf("%d\n",containValue(-1,&table));
- freeHashTable(&table);
- system("pause");
- return 0;
- }
- package linearList;
-
- /*
- * 采用链地址法实现哈希表
- * */
- class HashNode{
- int value;
- HashNode next;
-
- public HashNode(int value, HashNode next) {
- this.value = value;
- this.next = next;
- }
- }
- public class HashTable {
- HashNode hashNodes[];
- int size;
-
- public HashTable(int size) {
- this.size=size;
- this.hashNodes = new HashNode[size];
- for (int i = 0; i < size; i++) {
- hashNodes[i]=null;
- }
- }
- int getKey(int value){
- return value%size;
- }
- //向哈希表中插入数据
- HashTable addvalue(int value){
- int key = getKey(value);
- HashNode newNode = new HashNode(value, null);
- if (hashNodes[key]!=null){
- HashNode curNode=hashNodes[key];
- while (curNode.next!=null){
- curNode=curNode.next;
- };
- curNode.next=newNode;
- }else{
- hashNodes[key]=newNode;
- }
- return this;
- }
- //是否包含某值
- boolean containValue(int value){
- int key = getKey(value);
- if (hashNodes[key]==null){
- return false;
- }else{
- HashNode curNode=hashNodes[key];
- while (curNode!=null&&curNode.value!=value){
- curNode=curNode.next;
- }
- return curNode!=null?true:false;
- }
- }
- }
- class HashTableTest{
- public static void main(String[] args) {
- HashTable hashTable = new HashTable(10);
- hashTable.addvalue(11).addvalue(21).addvalue(13).addvalue(23).addvalue(4).addvalue(10);
- System.out.println(hashTable.containValue(24));
- }
- }
- #include
- #include
-
- #define SIZE 100
-
- typedef struct Node {
- int value;
- int key;
- struct Node* next;
- }Node;
-
- typedef struct {
- Node* node[SIZE];
- int magnification;
- }HashTable;
-
- void initHashTable(HashTable *ht){
- int i;
- for(i=0;i
- ht->node[i]=NULL;
- }
- ht->magnification=1;
- }
-
- //获取索引,-2:该元素已经无法插入,-1:非法值
- int getKey(int value,HashTable *ht){
- int key=value%SIZE;
- if(key>=0&&ht->node[key]!=NULL){
- int i;
- for(i=key+1;i
- if(ht->node[i]==NULL) return i;
- }
- return -2;
- }else if(ht->node[key]==NULL){
- return key;
- }
- return -1;
- }
-
- void pushToHt(int value,HashTable *ht){
- int key=getKey(value,ht);
- if(key==-1){
- printf("非法值的查找!\n");
- }else if(key==-2){
- printf("%d插入失败!\n",value);
- }else{
- Node *node=(Node*)malloc(sizeof(Node));
- node->key=key;
- node->value=value;
- node->next=NULL;
- ht->node[key]=node;
- }
- }
-
- int containValue(int value,HashTable *ht){
- int key=value%SIZE;
- if(key==-1){
- printf("查询非法数据!\n");
- return -1;
- }else{
- return ht->node[key]!=NULL&&ht->node[key]->value==value?1:0;
- }
- }
-
- int main(){
- HashTable ht;
- initHashTable(&ht);
- pushToHt(1,&ht);
- pushToHt(2,&ht);
- pushToHt(23,&ht);
- pushToHt(11,&ht);
- pushToHt(12,&ht);
- pushToHt(14,&ht);
- pushToHt(5,&ht);
- pushToHt(15,&ht);
- pushToHt(31,&ht);
- printf("%d\n",containValue(14,&ht));
- system("pause");
- return 0;
- }
开放寻址重点操作图解:
开放寻址法(java语言实现):
- package linearList;
-
- /*
- * 采用开放寻址法实现哈希表
- * */
- public class HashOpenTable{
- int values[];
- int size;
-
- public HashOpenTable(int size) {
- this.size=size;
- values=new int[size];
- for (int i = 0; i < size; i++) {
- values[i]=-1;
- }
- }
- //获取索引,-2:该元素已经无法插入,-1:非法值
- public int getKey(int value){
- int key=value%this.size;
- if (key>=0&&values[key]!=-1){
- for (int i = key+1; i < size; i++) {
- if (values[i]==-1) return i;
- }
- return -2;
- }else if (values[key]==-1){
- return key;
- }else {
- return -1;
- }
- }
- //向哈希表中插入数据
- HashOpenTable addvalue(int value){
- int key=getKey(value);
- if (key==-1){
- System.out.println("非法值的输入");
- }else if (key==-2){
- System.out.println("此数值不能插入哈希表!");
- }else {
- values[key]=value;
- }
- return this;
- }
- //查看哈希表中是否包含某值
- boolean containValue(int value){
- int key=value%this.size;
- if (key==-1)
- return false;
- else{
- for (int i = key; i < size; i++) {
- if (values[i]==value) return true;
- }
- return false;
- }
- }
- }
- class HashOpenTableTest{
- public static void main(String[] args) {
- HashOpenTable hashOpenTable = new HashOpenTable(10);
- hashOpenTable.addvalue(1).addvalue(2).addvalue(4).addvalue(12).addvalue(14);
- System.out.println(hashOpenTable.containValue(12));
- }
- }
-
相关阅读:
【Oracle APEX开发小技巧2】在不通过类型转换的前提下使用Oracle APEX自带的格式掩码实现数值的精确展现
安全狗安装
如何给R128在FreeRTOS下配置/data目录
Python 教程之从头开始构建个人助理,如何在 Python 中构建概念验证个人助理:意图分类、语音到文本和文本到语音(教程含源码)
入门力扣自学笔记190 C++ (题目编号:481)
c# winform程序,DispatcherTimer被调用延迟,响应间隔长
栈——火车进出栈问题(卡特兰数,组合计数+高精度乘法+筛质数+求n的阶乘里的质因数次数(模板))
Flask 学习-78.Flask-SQLAlchemy 一对多关系
【JQuery_Ajax_方法使用】Ajax的JQuery函数/方法
URL组成及对应的编程变量
-
原文地址:https://blog.csdn.net/m0_57254953/article/details/133843953