hash table相关2

2019年12月06日 阅读数:147
这篇文章主要向大家介绍hash table相关2,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

引入哈希桶的概念来实现一个哈希表

学习一下国外大牛的思路
服务器君一共花费  30.361 ms 进行了  4 次数据库查询,努力地为您提供了这个页面。

前面的讲述了如何用链地址法实现一个哈希表,那么今天来分析一下另外一种解决哈希冲突的作法,即为每一个Hash值,创建一个Hash桶(Bucket),桶的容量是固定的,也就是只能处理固定次数的冲突,如1048576个Hash桶,每一个桶中有4个表项(Entry),总计4M个表项。其实这两种的实现思路雷同,就是对Hash表中每一个Hash值创建一个冲突表,即将冲突的几个记录以表的形式存储在其中。html

大体的思路是这样的:算法

首先哈希桶的个数是固定的,有用户构建的时候输入,一旦构建,个数就已经固定;查找的时候首先将key值经过哈希函数获取哈希值,根据哈希值获取到对应的哈希桶,而后遍历哈希桶内的pairs数组获取。数据库

主要的数据结构:swift

01 struct Pair {
02     char *key;
03     char *value;
04 };
05  
06 struct Bucket {
07     unsigned int count;
08     Pair *pairs;
09 };
10  
11 struct StrMap {
12     unsigned int count;
13     Bucket *buckets;
14 };
  • 本小节主要是学习一下国外大牛是如何实现哈希表的。完整的代码,请看: 这里,一位圣安德鲁斯大学的讲师: KRISTENSSON博客

strmap.h数组

001 #ifndef _STRMAP_H_
002 #define _STRMAP_H_
003  
004 #ifdef __cplusplus
005 extern "C"
006 {
007 #endif
008  
009 #include <stdlib.h>
010 #include <string.h>
011  
012 typedef struct StrMap StrMap;
013  
014 /*
015  * This callback function is called once per key-value when iterating over
016  * all keys associated to values.
017  *
018  * Parameters:
019  *
020  * key: A pointer to a null-terminated C string. The string must not
021  * be modified by the client.
022  *
023  * value: A pointer to a null-terminated C string. The string must
024  * not be modified by the client.
025  *
026  * obj: A pointer to a client-specific object. This parameter may be
027  * null.
028  *
029  * Return value: None.
030  */
031 typedef void(*sm_enum_func)(const char *key, const char *value, const void*obj);
032  
033 /*
034  * Creates a string map.
035  *
036  * Parameters:
037  *
038  * capacity: The number of top-level slots this string map
039  * should allocate. This parameter must be > 0.
040  *
041  * Return value: A pointer to a string map object,
042  * or null if a new string map could not be allocated.
043  */
044 StrMap * sm_new(unsigned int capacity);
045  
046 /*
047  * Releases all memory held by a string map object.
048  *
049  * Parameters:
050  *
051  * map: A pointer to a string map. This parameter cannot be null.
052  * If the supplied string map has been previously released, the
053  * behaviour of this function is undefined.
054  *
055  * Return value: None.
056  */
057 void sm_delete(StrMap *map);
058  
059 /*
060  * Returns the value associated with the supplied key.
061  *
062  * Parameters:
063  *
064  * map: A pointer to a string map. This parameter cannot be null.
065  *
066  * key: A pointer to a null-terminated C string. This parameter cannot
067  * be null.
068  *
069  * out_buf: A pointer to an output buffer which will contain the value,
070  * if it exists and fits into the buffer.
071  *
072  * n_out_buf: The size of the output buffer in bytes.
073  *
074  * Return value: If out_buf is set to null and n_out_buf is set to 0 the return
075  * value will be the number of bytes required to store the value (if it exists)
076  * and its null-terminator. For all other parameter configurations the return value
077  * is 1 if an associated value was found and completely copied into the output buffer,
078  * 0 otherwise.
079  */
080 int sm_get(const StrMap *map, const char *key, char *out_buf, unsigned intn_out_buf);
081  
082 /*
083  * Queries the existence of a key.
084  *
085  * Parameters:
086  *
087  * map: A pointer to a string map. This parameter cannot be null.
088  *
089  * key: A pointer to a null-terminated C string. This parameter cannot
090  * be null.
091  *
092  * Return value: 1 if the key exists, 0 otherwise.
093  */
094 int sm_exists(const StrMap *map, const char *key);
095  
096 /*
097  * Associates a value with the supplied key. If the key is already
098  * associated with a value, the previous value is replaced.
099  *
100  * Parameters:
101  *
102  * map: A pointer to a string map. This parameter cannot be null.
103  *
104  * key: A pointer to a null-terminated C string. This parameter
105  * cannot be null. The string must have a string length > 0. The
106  * string will be copied.
107  *
108  * value: A pointer to a null-terminated C string. This parameter
109  * cannot be null. The string must have a string length > 0. The
110  * string will be copied.
111  *
112  * Return value: 1 if the association succeeded, 0 otherwise.
113  */
114 int sm_put(StrMap *map, const char *key, const char *value);
115  
116 /*
117  * Returns the number of associations between keys and values.
118  *
119  * Parameters:
120  *
121  * map: A pointer to a string map. This parameter cannot be null.
122  *
123  * Return value: The number of associations between keys and values.
124  */
125 int sm_get_count(const StrMap *map);
126  
127 /*
128  * An enumerator over all associations between keys and values.
129  *
130  * Parameters:
131  *
132  * map: A pointer to a string map. This parameter cannot be null.
133  *
134  * enum_func: A pointer to a callback function that will be
135  * called by this procedure once for every key associated
136  * with a value. This parameter cannot be null.
137  *
138  * obj: A pointer to a client-specific object. This parameter will be
139  * passed back to the client's callback function. This parameter can
140  * be null.
141  *
142  * Return value: 1 if enumeration completed, 0 otherwise.
143  */
144 int sm_enum(const StrMap *map, sm_enum_func enum_func, const void *obj);
145  
146 #ifdef __cplusplus
147 }
148 #endif
149  
150 #endif

strmap.c服务器

001 #include "strmap.h"
002  
003 typedef struct Pair Pair;
004  
005 typedef struct Bucket Bucket;
006  
007 struct Pair {
008     char *key;
009     char *value;
010 };
011  
012 struct Bucket {
013     unsigned int count;
014     Pair *pairs;
015 };
016  
017 struct StrMap {
018     unsigned int count;
019     Bucket *buckets;
020 };
021  
022 static Pair * get_pair(Bucket *bucket, const char *key);
023 static unsigned long hash(const char *str);
024  
025 StrMap * sm_new(unsigned int capacity)
026 {
027     StrMap *map;
028      
029     map = malloc(sizeof(StrMap));
030     if (map == NULL) {
031         return NULL;
032     }
033     map->count = capacity;
034     map->buckets = malloc(map->count * sizeof(Bucket));
035     if (map->buckets == NULL) {
036         free(map);
037         return NULL;
038     }
039     memset(map->buckets, 0, map->count * sizeof(Bucket));
040     return map;
041 }
042  
043 void sm_delete(StrMap *map)
044 {
045     unsigned int i, j, n, m;
046     Bucket *bucket;
047     Pair *pair;
048  
049     if (map == NULL) {
050         return;
051     }
052     n = map->count;
053     bucket = map->buckets;
054     i = 0;
055     while (i < n) {
056         m = bucket->count;
057         pair = bucket->pairs;
058         j = 0;
059         while(j < m) {
060             free(pair->key);
061             free(pair->value);
062             pair++;
063             j++;
064         }
065         free(bucket->pairs);
066         bucket++;
067         i++;
068     }
069     free(map->buckets);
070     free(map);
071 }
072  
073 int sm_get(const StrMap *map, const char *key, char *out_buf, unsigned intn_out_buf)
074