当前位置：网站首页>[hash table] a very simple zipper hash structure, so that the effect is too poor, there are too many conflicts, and the linked list is too long

[hash table] a very simple zipper hash structure, so that the effect is too poor, there are too many conflicts, and the linked list is too long

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

Preface

The sword soul of rain returns to the fairyland , All swords are broken 、 Ten thousand swords roar together , Ten thousand swords return to one ！
Insert picture description here

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

Catalog

Hash.h

// Hashtable --------------------------------------------
// Capacity of hash table , Every void is a bucket bucket 
#define Hash_BUCKET_SIZE 128
// Hash element 
typedef struct Hash_kv{
    
	struct Hash_kv* next;
	SS* k;
	void* v;
}Hash_kv;
// Hashtable 
typedef struct Hash {
    
	struct Hash_kv* tab[Hash_BUCKET_SIZE];
}Hash;

Hash* newHash();
u4 putHash(Hash* h,SS* key, void* value);		//push Is to add... From the back ,put It's insertion 
void* findHash(Hash* h,SS* key, u4 hashcode);	// Need to find , So it's not at
u4 hash(SS* key);
void printHash(Hash* h, void(*print)(void*));

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

Hash.c

Hash* newHash() {
    

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

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

	return h;
}



u4 putHash(Hash* h, SS* key, void* value) {
    
	ASSERT(h == null, " The hash table is empty ");

	ASSERT(key == null, " Input key It's empty ");
	ASSERT(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 % Hash_BUCKET_SIZE;
	if (h->tab[tmp] == null) {
      // No conflict 
		Hash_kv* kv = (Hash_kv*)malloc(24); 
		ASSERT(kv == null, "Hash_kv Create failure 1");

		kv->k = key;
		kv->v = value;
		kv->next = null;

		h->tab[tmp] = kv;		
	}
	else {
    	  // There are conflicts 
		// Add it to the back of the linked list 
		Hash_kv* it = h->tab[tmp];
		for (; it->next != null; it = it->next){
    }
			

		Hash_kv* kv = (Hash_kv*)malloc(24);	  
		ASSERT(kv == null, "Hash_kv Create failure 2");

		kv->k = key;
		kv->v = value;
		kv->next = null;

		it->next = kv;
	}

	return hashcode;
}


void* findHash(Hash* h, SS* key, u4 hashcode) {
    
	ASSERT(h == null, " The hash table is empty ");

	ASSERT(key == null, " Input key It's empty ");

	Hash_kv* it = h->tab[hashcode % Hash_BUCKET_SIZE];

	// This is empty 
	if (it == null)	
		return null;

	// It happens to be this 
	if (it->next == null) {
    
		if (equalSS(it->k,key))
			return it->v;
		else
			return null;
	}

	// It may be on the linked list 
	while (equalSS(it->k, key) == false) {
    
		it = it->next;
		if (it == null)
			return null;
	}
	return it->v;
}
	




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

	ASSERT(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 printHash(Hash* h, void(*print)(void*)) {
    
	ASSERT(h == null, " The hash table is empty ");
	
	for (u4 i = 0; i < Hash_BUCKET_SIZE; ++i) {
    
		printf("[%5d]",i);
		Hash_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");
	}

}

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

Usage method

u8 start_time = GetTickCount64();

	// Test hash table 
	Hash* h = newHash();

#define NUM 300 

	char v1[20], v2[20];
	static u4 hashcode[NUM];
	static SS* key[NUM];
	static SS* value[NUM];

	for (u4 i = 0; i < NUM; ++i) {
    
		key[i] = newSS(20);		
		memset(v1, 0, 20);
		sprintf(v1, "[email protected]%d", i);
		moveSS(key[i], v1, 0, 19);
		
		value[i] = newSS(20);
		memset(v2, 0, 20);
		sprintf(v2, "[email protected]%d", i);
		moveSS(value[i], v2, 0, 19);
									 		
		hashcode[i] = putHash(h, key[i], value[i]);
		//printf("[%5d] %d\n", i,hashcode[i] % Hash_BUCKET_SIZE);
	}

	printHash(h, myprint);
	

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

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

result

[    0]
[    1]
[    2]
[    3]
[    4]
[    5]
[    6]
[    7]
[    8]
[    9]
[   10]
[   11]
[   12]
[   13]
[   14]
[   15]
[   16]
[   17]
[   18]
[   19]
[   20][[email protected]100,[email protected]100]
[   21][[email protected]101,[email protected]101]
[   22][[email protected]102,[email protected]102]
[   23][[email protected]103,[email protected]103]->[[email protected]110,[email protected]110]
[   24][[email protected]104,[email protected]104]->[[email protected]111,[email protected]111]
[   25][[email protected]105,[email protected]105]->[[email protected]112,[email protected]112]
[   26][[email protected]106,[email protected]106]->[[email protected]113,[email protected]113]->[[email protected]120,[email protected]120]
[   27][[email protected]107,[email protected]107]->[[email protected]114,[email protected]114]->[[email protected]121,[email protected]121]
[   28][[email protected]108,[email protected]108]->[[email protected]115,[email protected]115]->[[email protected]122,[email protected]122]
[   29][[email protected]109,[email protected]109]->[[email protected]116,[email protected]116]->[[email protected]123,[email protected]123]->[[email protected]130,[email protected]130]->[[email protected]200,[email protected]200]
[   30][[email protected]117,[email protected]117]->[[email protected]124,[email protected]124]->[[email protected]131,[email protected]131]->[[email protected]201,[email protected]201]
[   31][[email protected]118,[email protected]118]->[[email protected]125,[email protected]125]->[[email protected]132,[email protected]132]->[[email protected]202,[email protected]202]
[   32][[email protected]119,[email protected]119]->[[email protected]126,[email protected]126]->[[email protected]133,[email protected]133]->[[email protected]140,[email protected]140]->[[email protected]203,[email protected]203]->[[email protected]210,[email protected]210]
[   33][[email protected]127,[email protected]127]->[[email protected]134,[email protected]134]->[[email protected]141,[email protected]141]->[[email protected]204,[email protected]204]->[[email protected]211,[email protected]211]
[   34][[email protected]128,[email protected]128]->[[email protected]135,[email protected]135]->[[email protected]142,[email protected]142]->[[email protected]205,[email protected]205]->[[email protected]212,[email protected]212]
[   35][[email protected]129,[email protected]129]->[[email protected]136,[email protected]136]->[[email protected]143,[email protected]143]->[[email protected]150,[email protected]150]->[[email protected]206,[email protected]206]->[[email protected]213,[email protected]213]->[[email protected]220,[email protected]220]
[   36][[email protected]137,[email protected]137]->[[email protected]144,[email protected]144]->[[email protected]151,[email protected]151]->[[email protected]207,[email protected]207]->[[email protected]214,[email protected]214]->[[email protected]221,[email protected]221]
[   37][[email protected]138,[email protected]138]->[[email protected]145,[email protected]145]->[[email protected]152,[email protected]152]->[[email protected]208,[email protected]208]->[[email protected]215,[email protected]215]->[[email protected]222,[email protected]222]
[   38][[email protected]139,[email protected]139]->[[email protected]146,[email protected]146]->[[email protected]153,[email protected]153]->[[email protected]160,[email protected]160]->[[email protected]209,[email protected]209]->[[email protected]216,[email protected]216]->[[email protected]223,[email protected]223]->[[email protected]230,[email protected]230]
[   39][[email protected]147,[email protected]147]->[[email protected]154,[email protected]154]->[[email protected]161,[email protected]161]->[[email protected]217,[email protected]217]->[[email protected]224,[email protected]224]->[[email protected]231,[email protected]231]
[   40][[email protected]148,[email protected]148]->[[email protected]155,[email protected]155]->[[email protected]162,[email protected]162]->[[email protected]218,[email protected]218]->[[email protected]225,[email protected]225]->[[email protected]232,[email protected]232]
[   41][[email protected]149,[email protected]149]->[[email protected]156,[email protected]156]->[[email protected]163,[email protected]163]->[[email protected]170,[email protected]170]->[[email protected]219,[email protected]219]->[[email protected]226,[email protected]226]->[[email protected]233,[email protected]233]->[[email protected]240,[email protected]240]
[   42][[email protected]157,[email protected]157]->[[email protected]164,[email protected]164]->[[email protected]171,[email protected]171]->[[email protected]227,[email protected]227]->[[email protected]234,[email protected]234]->[[email protected]241,[email protected]241]
[   43][[email protected]158,[email protected]158]->[[email protected]165,[email protected]165]->[[email protected]172,[email protected]172]->[[email protected]228,[email protected]228]->[[email protected]235,[email protected]235]->[[email protected]242,[email protected]242]
[   44][[email protected]159,[email protected]159]->[[email protected]166,[email protected]166]->[[email protected]173,[email protected]173]->[[email protected]180,[email protected]180]->[[email protected]229,[email protected]229]->[[email protected]236,[email protected]236]->[[email protected]243,[email protected]243]->[[email protected]250,[email protected]250]
[   45][[email protected]167,[email protected]167]->[[email protected]174,[email protected]174]->[[email protected]181,[email protected]181]->[[email protected]237,[email protected]237]->[[email protected]244,[email protected]244]->[[email protected]251,[email protected]251]
[   46][[email protected]168,[email protected]168]->[[email protected]175,[email protected]175]->[[email protected]182,[email protected]182]->[[email protected]238,[email protected]238]->[[email protected]245,[email protected]245]->[[email protected]252,[email protected]252]
[   47][[email protected]169,[email protected]169]->[[email protected]176,[email protected]176]->[[email protected]183,[email protected]183]->[[email protected]190,[email protected]190]->[[email protected]239,[email protected]239]->[[email protected]246,[email protected]246]->[[email protected]253,[email protected]253]->[[email protected]260,[email protected]260]
[   48][[email protected]177,[email protected]177]->[[email protected]184,[email protected]184]->[[email protected]191,[email protected]191]->[[email protected]247,[email protected]247]->[[email protected]254,[email protected]254]->[[email protected]261,[email protected]261]
[   49][[email protected]178,[email protected]178]->[[email protected]185,[email protected]185]->[[email protected]192,[email protected]192]->[[email protected]248,[email protected]248]->[[email protected]255,[email protected]255]->[[email protected]262,[email protected]262]
[   50][[email protected]179,[email protected]179]->[[email protected]186,[email protected]186]->[[email protected]193,[email protected]193]->[[email protected]249,[email protected]249]->[[email protected]256,[email protected]256]->[[email protected]263,[email protected]263]->[[email protected]270,[email protected]270]
[   51][  [email protected]0,  [email protected]0]->[[email protected]187,[email protected]187]->[[email protected]194,[email protected]194]->[[email protected]257,[email protected]257]->[[email protected]264,[email protected]264]->[[email protected]271,[email protected]271]
[   52][  [email protected]1,  [email protected]1]->[[email protected]188,[email protected]188]->[[email protected]195,[email protected]195]->[[email protected]258,[email protected]258]->[[email protected]265,[email protected]265]->[[email protected]272,[email protected]272]
[   53][  [email protected]2,  [email protected]2]->[[email protected]189,[email protected]189]->[[email protected]196,[email protected]196]->[[email protected]259,[email protected]259]->[[email protected]266,[email protected]266]->[[email protected]273,[email protected]273]->[[email protected]280,[email protected]280]
[   54][  [email protected]3,  [email protected]3]->[[email protected]197,[email protected]197]->[[email protected]267,[email protected]267]->[[email protected]274,[email protected]274]->[[email protected]281,[email protected]281]
[   55][  [email protected]4,  [email protected]4]->[[email protected]198,[email protected]198]->[[email protected]268,[email protected]268]->[[email protected]275,[email protected]275]->[[email protected]282,[email protected]282]
[   56][  [email protected]5,  [email protected]5]->[[email protected]199,[email protected]199]->[[email protected]269,[email protected]269]->[[email protected]276,[email protected]276]->[[email protected]283,[email protected]283]->[[email protected]290,[email protected]290]
[   57][  [email protected]6,  [email protected]6]->[[email protected]277,[email protected]277]->[[email protected]284,[email protected]284]->[[email protected]291,[email protected]291]
[   58][  [email protected]7,  [email protected]7]->[[email protected]278,[email protected]278]->[[email protected]285,[email protected]285]->[[email protected]292,[email protected]292]
[   59][  [email protected]8,  [email protected]8]->[[email protected]279,[email protected]279]->[[email protected]286,[email protected]286]->[[email protected]293,[email protected]293]
[   60][  [email protected]9,  [email protected]9]->[[email protected]287,[email protected]287]->[[email protected]294,[email protected]294]
[   61][[email protected]288,[email protected]288]->[[email protected]295,[email protected]295]
[   62][[email protected]289,[email protected]289]->[[email protected]296,[email protected]296]
[   63][[email protected]297,[email protected]297]
[   64][[email protected]298,[email protected]298]
[   65][[email protected]299,[email protected]299]
[   66]
[   67]
[   68]
[   69]
[   70]
[   71]
[   72]
[   73]
[   74]
[   75]
[   76][ [email protected]10, [email protected]10]
[   77][ [email protected]11, [email protected]11]
[   78][ [email protected]12, [email protected]12]
[   79][ [email protected]13, [email protected]13]->[ [email protected]20, [email protected]20]
[   80][ [email protected]14, [email protected]14]->[ [email protected]21, [email protected]21]
[   81][ [email protected]15, [email protected]15]->[ [email protected]22, [email protected]22]
[   82][ [email protected]16, [email protected]16]->[ [email protected]23, [email protected]23]->[ [email protected]30, [email protected]30]
[   83][ [email protected]17, [email protected]17]->[ [email protected]24, [email protected]24]->[ [email protected]31, [email protected]31]
[   84][ [email protected]18, [email protected]18]->[ [email protected]25, [email protected]25]->[ [email protected]32, [email protected]32]
[   85][ [email protected]19, [email protected]19]->[ [email protected]26, [email protected]26]->[ [email protected]33, [email protected]33]->[ [email protected]40, [email protected]40]
[   86][ [email protected]27, [email protected]27]->[ [email protected]34, [email protected]34]->[ [email protected]41, [email protected]41]
[   87][ [email protected]28, [email protected]28]->[ [email protected]35, [email protected]35]->[ [email protected]42, [email protected]42]
[   88][ [email protected]29, [email protected]29]->[ [email protected]36, [email protected]36]->[ [email protected]43, [email protected]43]->[ [email protected]50, [email protected]50]
[   89][ [email protected]37, [email protected]37]->[ [email protected]44, [email protected]44]->[ [email protected]51, [email protected]51]
[   90][ [email protected]38, [email protected]38]->[ [email protected]45, [email protected]45]->[ [email protected]52, [email protected]52]
[   91][ [email protected]39, [email protected]39]->[ [email protected]46, [email protected]46]->[ [email protected]53, [email protected]53]->[ [email protected]60, [email protected]60]
[   92][ [email protected]47, [email protected]47]->[ [email protected]54, [email protected]54]->[ [email protected]61, [email protected]61]
[   93][ [email protected]48, [email protected]48]->[ [email protected]55, [email protected]55]->[ [email protected]62, [email protected]62]
[   94][ [email protected]49, [email protected]49]->[ [email protected]56, [email protected]56]->[ [email protected]63, [email protected]63]->[ [email protected]70, [email protected]70]
[   95][ [email protected]57, [email protected]57]->[ [email protected]64, [email protected]64]->[ [email protected]71, [email protected]71]
[   96][ [email protected]58, [email protected]58]->[ [email protected]65, [email protected]65]->[ [email protected]72, [email protected]72]
[   97][ [email protected]59, [email protected]59]->[ [email protected]66, [email protected]66]->[ [email protected]73, [email protected]73]->[ key@80, [email protected]80]
[   98][ [email protected]67, [email protected]67]->[ [email protected]74, [email protected]74]->[ [email protected]81, [email protected]81]
[   99][ [email protected]68, [email protected]68]->[ [email protected]75, [email protected]75]->[ [email protected]82, [email protected]82]
[  100][ [email protected]69, [email protected]69]->[ [email protected]76, [email protected]76]->[ [email protected]83, [email protected]83]->[ [email protected]90, [email protected]90]
[  101][ [email protected]77, [email protected]77]->[ [email protected]84, [email protected]84]->[ [email protected]91, [email protected]91]
[  102][ [email protected]78, [email protected]78]->[ [email protected]85, [email protected]85]->[ [email protected]92, [email protected]92]
[  103][ [email protected]79, [email protected]79]->[ [email protected]86, [email protected]86]->[ [email protected]93, [email protected]93]
[  104][ [email protected]87, [email protected]87]->[ [email protected]94, [email protected]94]
[  105][ [email protected]88, [email protected]88]->[ [email protected]95, [email protected]95]
[  106][ [email protected]89, [email protected]89]->[ [email protected]96, [email protected]96]
[  107][ [email protected]97, [email protected]97]
[  108][ [email protected]98, [email protected]98]
[  109][ [email protected]99, [email protected]99]
[  110]
[  111]
[  112]
[  113]
[  114]
[  115]
[  116]
[  117]
[  118]
[  119]
[  120]
[  121]
[  122]
[  123]
[  124]
[  125]
[  126]
[  127]
cost 203 ms