哈希表查找

By C++

  1. #include <stdio.h>
  2. #define MaxSize 100        /*哈希表最大长度*/
  4. typedef int KeyType;
  6. typedef struct
  7. {
  8.     KeyType key;    /*关键字值*/
  9.     int si;            /*探查次数*/
  10. } HashTable;
  12. void CreateHT(HashTable ht[],KeyType a[],int n,int m,int p)    /*构造哈希表*/
  13. {
  14.     int i,d,cnt;
  15.     for (i=0;i<m;i++)  /*置初值*/
  16.     {
  17.         ht[i].key=0;
  18.         ht[i].si=0;
  19.     }
  20.     for (i=0;i<n;i++)
  21.     {
  22.         cnt=1;            /*累计探查次数*/
  23.         d=a[i]%p;
  24.         if (ht[d].key==0)
  25.         {
  26.             ht[d].key=a[i];
  27.             ht[d].si=cnt;
  28.         }
  29.         else
  30.         {
  31.             do            /*处理冲突*/
  32.             {
  33.                 d=(d+1)%m;
  34.                 cnt++;
  35.             } while (ht[d].key!=0);
  36.             ht[d].key=a[i];
  37.             ht[d].si=cnt;
  38.         }
  39.     }
  40. }
  42. void DispHT(HashTable ht[],int n,int m)    /*输出哈希表*/
  43. {
  44.     int i;
  45.     double avg;
  46.     printf("i:  ");
  47.     for (i=0;i<m;i++) 
  48.         printf("%-3d",i);
  49.     printf("\n");
  50.     printf("key:");
  51.     for (i=0;i<m;i++) 
  52.         printf("%-3d",ht[i].key);
  53.     printf("\n");
  54.     printf("si: ");
  55.     for (i=0;i<m;i++) 
  56.         printf("%-3d",ht[i].si);
  57.     printf("\n");
  58.     avg=0;
  59.     for (i=0;i<m;i++) 
  60.         avg+=ht[i].si;
  61.     avg=avg/n;
  62.     printf("平均查找长度:ASL(%d)=%g\n",n,avg);
  63. }
  65. void main()
  66. {
  67.     HashTable ht[MaxSize];
  68.     KeyType a[]={19,1,23,14,55,20,84,27,68,11,10,77};
  69.     int n=12,m=19,p=13;
  70.     CreateHT(ht,a,n,m,p);
  71.     DispHT(ht,n,m);
  72. }

By Golang

  1. // Package hashtable creates a ValueHashtable data structure for the Item type
  2. package hashtable
  4. import (
  5.     "fmt"
  6.     "sync"
  7. )
  9. // Key the key of the dictionary
  10. type Key interface{}
  12. // Value the content of the dictionary
  13. type Value interface{}
  15. // ValueHashtable the set of Items
  16. type ValueHashtable struct {
  17.     items map[int]Value
  18.     lock  sync.RWMutex
  19. }
  21. // the hash() private function uses the famous Horner's method
  22. // to generate a hash of a string with O(n) complexity
  23. func hash(k Key) int {
  24.     key := fmt.Sprintf("%s", k)
  25.     h := 0
  26.     for i := 0; i < len(key); i++ {
  27.         h = 31*h + int(key[i])
  28.     }
  29.     return h
  30. }
  32. // Put item with value v and key k into the hashtable
  33. func (ht *ValueHashtable) Put(k Key, v Value) {
  34.     ht.lock.Lock()
  35.     defer ht.lock.Unlock()
  36.     i := hash(k)
  37.     if ht.items == nil {
  38.         ht.items = make(map[int]Value)
  39.     }
  40.     ht.items[i] = v
  41. }
  43. // Remove item with key k from hashtable
  44. func (ht *ValueHashtable) Remove(k Key) {
  45.     ht.lock.Lock()
  46.     defer ht.lock.Unlock()
  47.     i := hash(k)
  48.     delete(ht.items, i)
  49. }
  51. // Get item with key k from the hashtable
  52. func (ht *ValueHashtable) Get(k Key) Value {
  53.     ht.lock.RLock()
  54.     defer ht.lock.RUnlock()
  55.     i := hash(k)
  56.     return ht.items[i]
  57. }
  59. // Size returns the number of the hashtable elements
  60. func (ht *ValueHashtable) Size() int {
  61.     ht.lock.RLock()
  62.     defer ht.lock.RUnlock()
  63.     return len(ht.items)
  64. }