• 哈希表查找
    • By C++
    • By Golang

    哈希表查找

    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. }