当前位置：网站首页>[hash table] improved, zipper hash structure - directly use two indexes to search, instead of hashing and% every time

[hash table] improved, zipper hash structure - directly use two indexes to search, instead of hashing and% every time

2022-06-26 03:17:00 【Su Nianxin】

Preface

Insert picture description here

The ancient god broke the sky with his strength , Ancient demons killed against the sky , The ancient demon turned his hand and killed the way ！

$\;\\\;\\\;$

Catalog

Hash.h

// Capacity of hash table , Every void is a bucket bucket 
#define HashTable_BUCKET_SIZE 50
// Hash coordinates 
typedef struct HashTable_coord{
    
	u4 i;	// Array index 
	u4 j;	// Position on linked list , from 0 Start 
}HashTable_coord;
// Hash element 
typedef struct HashTable_kv{
    
	struct HashTable_kv* next;
	HashTable_coord co;
	STRING* k;
	void* v;
}HashTable_kv;
// Hashtable 
typedef struct HashTable {
    
	struct HashTable_kv* tab[HashTable_BUCKET_SIZE];
}HashTable;

HashTable* newHashTable();
void destroyHashTable(HashTable* h);							
HashTable_coord* putHashTable(HashTable* h,STRING* key, void* value);	//push Is to add... From the back ,put It's insertion 
void* atHashTable(HashTable* h, HashTable_coord* co);
void delHashTable(HashTable* h, HashTable_coord* co);	
u4 hash(STRING* key);
void printHashTable(HashTable* h, void(*print)(void*));
void printkvHashTable(HashTable* h,u4 position,void(*print)(void*));

$\;\\\;\\\;$

Hash.c

HashTable* newHashTable() {
    

	HashTable* h = (HashTable*)malloc(sizeof(HashTable));
	ASTRINGERT(h == null, " Hash table creation failed ");

	for (u4 i = 0; i < HashTable_BUCKET_SIZE; ++i)
		h->tab[i] = null;
	return h;
}



void destroyHashTable(HashTable* h) {
    
	ASTRINGERT(h == null, " The hash table is empty ");

	if (h!= null) 
		free(h);
}








HashTable_coord* putHashTable(HashTable* h, STRING* key, void* value) {
    
	ASTRINGERT(h == null, " The hash table is empty ");

	ASTRINGERT(key == null, " Input key It's empty ");
	ASTRINGERT(value == null, " Input value It's empty ");	// There is no such thing as name An identifier without a value 


	u4 hashcode = hash(key);
	
	// See if there's any conflict 
	u4 tmp = hashcode % HashTable_BUCKET_SIZE;
	if (h->tab[tmp] == null) {
      // No conflict 
		HashTable_kv* kv = (HashTable_kv*)malloc(sizeof(HashTable_kv));
		ASTRINGERT(kv == null, "HashTable_kv Create failure 1");

		kv->co.i = tmp;
		kv->co.j = 0;
		kv->k = key;
		kv->v = value;
		kv->next = null;

		h->tab[tmp] = kv;	
		return &(kv->co);
	}
	else {
    	  // There are conflicts 
		// Add it to the back of the linked list 
		HashTable_kv* it = h->tab[tmp];
		u4 p = 1;
		for (; it->next != null; it = it->next,++p){
    }
			
		// Create a new kv
		HashTable_kv* kv = (HashTable_kv*)malloc(sizeof(HashTable_kv));	  
		ASTRINGERT(kv == null, "HashTable_kv Create failure 2");

		kv->co.i = tmp;
		kv->co.j = p;
		kv->k = key;
		kv->v = value;
		kv->next = null;

		it->next = kv;
		return &(kv->co);
	}

}


void* atHashTable(HashTable* h, HashTable_coord* co) {
    
	ASTRINGERT(h == null, " The hash table is empty ");	  	
	ASTRINGERT(co->i > HashTable_BUCKET_SIZE, " Illegal hash array index ");

	HashTable_kv* it = h->tab[co->i];
	for (u4 i = 0;i<=co->j; ++i,it=it->next)  
		if (it == null)
			return null;// Did not find  , None of the elements found before are empty 
	return it->v;

}
	




void delHashTable(HashTable* h, HashTable_coord* co) {
    
	ASTRINGERT(h == null, " The hash table is empty ");
	ASTRINGERT(co->i >= HashTable_BUCKET_SIZE, " Illegal hash array index ");

	HashTable_kv* it = h->tab[co->i];
	if (it == null)
		return;// Keep the change. 

	// Delete header node , That's all 
	if (it->next == null) {
    
		h->tab[co->i] = null;
		return;
	}



	

	HashTable_kv* pre = &it;
	for (u4 i = 0; i < co->j ; ++i) {
    
		pre = it;
		it = it->next;
		if (it == null)
			return;
	}
	
	if (it->next != null) {
     // Not the last one  

		// hinder j You have to cut it by one 
		for (HashTable_kv* i = it->next; i != null; i=i->next)
			--i->co.j;

		*it = *(it->next);	// Move forward next 
	}
	else // the last one 
		pre->next = null;

}




u4 hash(STRING* key) {
    
	ASTRINGERT(key == null, " The security string is empty ");

	ASTRINGERT(key->len == 0, "hash The incoming string is empty ");
	
	//magic number
	u4 seed = 131;	/* 31 131 1313 13131 131313 etc.. */

	u4 h = 0;

	for (u4 i = 0; i < key->len; ++i)
		h =  (h * seed) + (key->s[i]) ;

	return h;
}



void printHashTable(HashTable* h, void(*print)(void*)) {
    
	ASTRINGERT(h == null, " The hash table is empty ");
	
	for (u4 i = 0; i < HashTable_BUCKET_SIZE; ++i) {
    
		printf("[%5d]",i);
		HashTable_kv* it = h->tab[i];
		if (it == null) {
    
			printf("\n");
			continue;
		}
		
		for (;it!=null;it=it->next) {
    
			printf("[%7s,", it->k->s);
			print(it->v);
			if (it->next != null)
				printf("]->");
			else
				printf("]");
		}
		printf("\n");
	}

}



void printkvHashTable(HashTable* h, u4 position,void(*print)(void*)) {
    
	ASTRINGERT(h == null, " The hash table is empty ");

	ASTRINGERT(position >= HashTable_BUCKET_SIZE, " Illegal location ");

	printf("[%5d]",position);
	HashTable_kv* it = h->tab[position];
	if (it == null) {
    
		printf("\n");
		return;
	}

	for (; it != null; it = it->next) {
    
		printf("[%7s,", it->k->s);
		print(it->v);
		if (it->next != null)
			printf("]->");
		else
			printf("]");
	}
	printf("\n");
}

$\;\\\;\\\;$

Usage method

	u8 start_time = GetTickCount64();
	// Test hash table 
	HashTable* h = newHashTable();

#define NUM 50 

	char v1[20], v2[20];
	static HashTable_coord* po[NUM];
	static STRING* key[NUM];
	static STRING* value[NUM];

	for (u4 i = 0; i < NUM; ++i) {
    
		key[i] = newSTRING(20);
		memset(v1, 0, 20);
		sprintf(v1, "[email protected]%d", i);
		moveSTRING(key[i], v1, 0, 19);

		value[i] = newSTRING(20);
		memset(v2, 0, 20);
		sprintf(v2, "[email protected]%d", i);
		moveSTRING(value[i], v2, 0, 19);

		po[i] = putHashTable(h, key[i], value[i]);
		
	}

	

	printHashTable(h, myprint);  	
	delHashTable(h, po[4]);
	printHashTable(h, myprint);

		

	printf("cost %llu ms\n", GetTickCount64() - start_time);

$\;\\\;\\\;$

result

[    0][ [email protected]36, [email protected]36]
[    1][ [email protected]37, [email protected]37]
[    2][ [email protected]38, [email protected]38]
[    3][ [email protected]39, [email protected]39]
[    4]
[    5]
[    6]
[    7]
[    8]
[    9]
[   10]
[   11]
[   12]
[   13][ [email protected]20, [email protected]20]
[   14][ [email protected]21, [email protected]21]
[   15][ [email protected]22, [email protected]22]
[   16][ [email protected]23, [email protected]23]
[   17][ [email protected]24, [email protected]24]
[   18][ [email protected]25, [email protected]25]
[   19][ [email protected]26, [email protected]26]
[   20][ [email protected]27, [email protected]27]
[   21][ [email protected]28, [email protected]28]
[   22][ [email protected]29, [email protected]29]
[   23]
[   24]
[   25][ [email protected]40, [email protected]40]
[   26][ [email protected]41, [email protected]41]
[   27][ [email protected]42, [email protected]42]
[   28][ [email protected]43, [email protected]43]
[   29][  [email protected]0,  [email protected]0]->[ [email protected]44, [email protected]44]
[   30][  [email protected]1,  [email protected]1]->[ [email protected]45, [email protected]45]
[   31][  [email protected]2,  [email protected]2]->[ [email protected]46, [email protected]46]
[   32][  [email protected]3,  [email protected]3]->[ [email protected]10, [email protected]10]->[ [email protected]47, [email protected]47]
[   33][  [email protected]4,  [email protected]4]->[ [email protected]11, [email protected]11]->[ [email protected]48, [email protected]48]
[   34][  [email protected]5,  [email protected]5]->[ [email protected]12, [email protected]12]->[ [email protected]49, [email protected]49]
[   35][  [email protected]6,  [email protected]6]->[ [email protected]13, [email protected]13]
[   36][  [email protected]7,  [email protected]7]->[ [email protected]14, [email protected]14]
[   37][  [email protected]8,  [email protected]8]->[ [email protected]15, [email protected]15]
[   38][  [email protected]9,  [email protected]9]->[ [email protected]16, [email protected]16]
[   39][ [email protected]17, [email protected]17]
[   40][ [email protected]18, [email protected]18]
[   41][ [email protected]19, [email protected]19]
[   42]
[   43]
[   44][ [email protected]30, [email protected]30]
[   45][ [email protected]31, [email protected]31]
[   46][ [email protected]32, [email protected]32]
[   47][ [email protected]33, [email protected]33]
[   48][ [email protected]34, [email protected]34]
[   49][ [email protected]35, [email protected]35]
[    0][ [email protected]36, [email protected]36]
[    1][ [email protected]37, [email protected]37]
[    2][ [email protected]38, [email protected]38]
[    3][ [email protected]39, [email protected]39]
[    4]
[    5]
[    6]
[    7]
[    8]
[    9]
[   10]
[   11]
[   12]
[   13][ [email protected]20, [email protected]20]
[   14][ [email protected]21, [email protected]21]
[   15][ [email protected]22, [email protected]22]
[   16][ [email protected]23, [email protected]23]
[   17][ [email protected]24, [email protected]24]
[   18][ [email protected]25, [email protected]25]
[   19][ [email protected]26, [email protected]26]
[   20][ [email protected]27, [email protected]27]
[   21][ [email protected]28, [email protected]28]
[   22][ [email protected]29, [email protected]29]
[   23]
[   24]
[   25][ [email protected]40, [email protected]40]
[   26][ [email protected]41, [email protected]41]
[   27][ [email protected]42, [email protected]42]
[   28][ [email protected]43, [email protected]43]
[   29][  [email protected]0,  [email protected]0]->[ [email protected]44, [email protected]44]
[   30][  [email protected]1,  [email protected]1]->[ [email protected]45, [email protected]45]
[   31][  [email protected]2,  [email protected]2]->[ [email protected]46, [email protected]46]
[   32][  [email protected]3,  [email protected]3]->[ [email protected]10, [email protected]10]->[ [email protected]47, [email protected]47]
[   33][ [email protected]11, [email protected]11]->[ [email protected]48, [email protected]48]
[   34][  [email protected]5,  [email protected]5]->[ [email protected]12, [email protected]12]->[ [email protected]49, [email protected]49]
[   35][  [email protected]6,  [email protected]6]->[ [email protected]13, [email protected]13]
[   36][  [email protected]7,  [email protected]7]->[ [email protected]14, [email protected]14]
[   37][  [email protected]8,  [email protected]8]->[ [email protected]15, [email protected]15]
[   38][  [email protected]9,  [email protected]9]->[ [email protected]16, [email protected]16]
[   39][ [email protected]17, [email protected]17]
[   40][ [email protected]18, [email protected]18]
[   41][ [email protected]19, [email protected]19]
[   42]
[   43]
[   44][ [email protected]30, [email protected]30]
[   45][ [email protected]31, [email protected]31]
[   46][ [email protected]32, [email protected]32]
[   47][ [email protected]33, [email protected]33]
[   48][ [email protected]34, [email protected]34]
[   49][ [email protected]35, [email protected]35]
cost 78 ms