生活随笔
收集整理的這篇文章主要介紹了
hash table(完全散列实现的哈希表)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
hash table(完全散列實現的哈希表)
完全散列
特點：靜態的，創建時候完成了散列表的生成。
不可以刪，也不可以增加數據。只可以修改數據。
內部用全域散列生成
#ifndef C11LEARN_HASHPERFECT_H
#define C11LEARN_HASHPERFECT_H
#include "KeyNode.h"
#include "HashUniversal.h"
template<typename T>
class HashPerfect
{
protected:HashUniversal
<T
>** array
;int capacity
;long long large_prime_numbers
;long long a
;long long b
;
private:HashPerfect(const HashPerfect
<T
>& hashUniversal
){};const HashPerfect
<T
>& operator=(const HashPerfect
<T
>& hashUniversal
){};
public:HashPerfect(KeyNode
<T
>*array
,int length
,int capacity
,long long large_prime_numbers
= 100001651);virtual ~HashPerfect();T
& operator[](int key
);protected:virtual int hashing(int key
);
};
template<typename T>
HashPerfect<T
>::HashPerfect(KeyNode
<T
>*arr
,int length
,int capacity
,long long large_prime_numbers
):capacity(capacity
),large_prime_numbers(large_prime_numbers
){array
= new HashUniversal
<T
>*[this->capacity
];int *int_array
= new int[this->capacity
]();a
= random_include_left_right(1ll,this->large_prime_numbers
-1);b
= random_include_left_right(0ll,this->large_prime_numbers
-1);for (int i
= 0; i
< length
; ++i
) {int_array
[hashing(arr
[i
].key
)] += 1;}for (int i
= 0; i
< this->capacity
; ++i
) {if(int_array
[i
] == 0){array
[i
] = nullptr;}else{array
[i
] = new HashUniversal
<T
>(int_array
[i
]*int_array
[i
],large_prime_numbers
);}}for (int i
= 0; i
< length
; ++i
) {(*array
[hashing(arr
[i
].key
)])[arr
[i
].key
] = arr
[i
].value
;}
}
template<typename T>
T
& HashPerfect
<T
>::operator[](int key
){if(array
[hashing(key
)] == nullptr)throw "no find";return (*array
[hashing(key
)])[key
];
}
template<typename T>
int HashPerfect<T
>::hashing(int key
){return ((a
*key
+b
)%large_prime_numbers
)%capacity
;
}
template<typename T>
HashPerfect
<T
>::~HashPerfect(){if(array
!= nullptr){for (int i
= 0; i
< capacity
; ++i
) {if(array
[i
]!= nullptr){delete array
[i
];array
[i
] = nullptr;}}delete[] array
;array
= nullptr;}}#endif
輔助類
1??KeyNode地址鏈接
2??HashUniversal地址鏈接
測試代碼
KeyNode
<string
> nodes
[] = {KeyNode
<string
>(0,"hello"),KeyNode
<string
>(1,"world"),};HashPerfect
<string
> hashPerfect(nodes
,2,20);cout
<<hashPerfect
[0]<<endl
;cout
<<hashPerfect
[1]<<endl
;hashPerfect
[1] = "you";cout
<<hashPerfect
[1]<<endl
;
總結
以上是生活随笔為你收集整理的hash table(完全散列实现的哈希表)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
