1 #ifndef HASHTABLE_H_

2 #define HASHTABLE_H_

3

4 #include <list>

5 #include <vector>

6

7 template <class KeyT, class ValT>

8 struct Pair {

9 KeyT key;

10 ValT val;

11 };

12

13 template <class KeyType, class ValType>

14 class HashTable {

15 private:

16

17 size_t size;

18 std::vector<std::list<Pair<KeyType, ValType> > > table;

19 //std::list<Pair<KeyType, ValType> > table[100];

20

21 unsigned int (*HashFunc)(const KeyType &key, unsigned long size);

22 unsigned int Hash(const KeyType &key) {return (unsigned int)HashFunc(key, (unsigned long)size);}

23

24 public:

25

26 HashTable(unsigned long size = 101);

27 ~HashTable();

28

29 void SetHashFunction(unsigned int (*HashFunc)(const KeyType&, unsigned long));

30

31 void Insert(KeyType key, ValType value);

32 void Remove(KeyType key);

33

34 Pair<KeyType, ValType> *Find(KeyType key);

35 };

36

37 //// std hash function

38 //template <class KeyType>

39 //unsigned int _HashFunction(const KeyType &key, unsigned long size) {

40 // return (size_t)key % size;

41 //}

42

43 // hash table member functions

44 template <class KeyType, class ValType>

45 HashTable<KeyType, ValType>::HashTable(unsigned long size) {

46 this->size = size;

47 //HashFunc = _HashFunction;

48 table.resize(size);

49 }

50

51 template <class KeyType, class ValType>

52 HashTable<KeyType, ValType>::~HashTable() {

53 for(unsigned long i=0; i<size; i++) {

54 table[i].erase(table[i].begin(), table[i].end());

55 }

56 }

57

58 template <class KeyType, class ValType>

59 void HashTable<KeyType, ValType>::SetHashFunction(unsigned int (*HashFunc)(const KeyType&, unsigned long)) {

60 this->HashFunc = HashFunc;

61 }

62

63 template <class KeyType, class ValType>

64 void HashTable<KeyType, ValType>::Insert(KeyType key, ValType value) {

65 Pair<KeyType, ValType> newpair;

66 newpair.key = key;

67 newpair.val = value;

68

69 table[Hash(key)].push_back(newpair);

70 }

71

72 template <class KeyType, class ValType>

73 void HashTable<KeyType, ValType>::Remove(KeyType key) {

74

75 unsigned int pos = Hash(key);

76

77 std::list<Pair<KeyType, ValType> >::iterator iter = table[pos].begin();

78 while(iter != table[pos].end()) {

79 if(iter->key == key) {

80 table[pos].erase(iter);

81 return;

82 }

83 iter++;

84 }

85 }

86

87 template <class KeyType, class ValType>

88 Pair<KeyType, ValType> *HashTable<KeyType, ValType>::Find(KeyType key) {

89

90 unsigned int pos = Hash(key);

91

92 std::list<Pair<KeyType, ValType> >::iterator iter = table[pos].begin();

93 while(iter != table[pos].end()) {

94 if(iter->key == key) {

95 return &(*iter);

96 }

97 iter++;

98 }

99

100 return 0;

101 }

102

103 #endif // HASHTABLE_H_