26 @released |
26 @released |
27 */ |
27 */ |
28 |
28 |
29 #include "common.h" |
29 #include "common.h" |
30 #include "hash.h" |
30 #include "hash.h" |
31 |
|
32 /** |
31 /** |
33 Constructor, intializes the table size |
32 Constructor, intializes the table size |
34 |
33 |
35 @internalComponent |
34 @internalComponent |
36 @released |
35 @released |
37 |
36 |
38 @param aSize - Hash table size (Number of dissimilar data can stored) |
37 @param aSize - Hash table size (Number of dissimilar data can stored) |
39 */ |
38 */ |
40 HashTable::HashTable(int aSize) |
39 HashTable::HashTable(int aSize) |
41 :iSize(aSize) |
40 :iSize(aSize) { |
42 { |
|
43 } |
41 } |
44 |
42 |
45 /** |
43 /** |
46 Destructor |
44 Destructor |
47 |
45 |
48 @internalComponent |
46 @internalComponent |
49 @released |
47 @released |
50 */ |
48 */ |
51 HashTable::~HashTable() |
49 HashTable::~HashTable() { |
52 { |
|
53 } |
50 } |
54 |
51 |
55 /** |
52 /** |
56 Function responsible to return the Hash value for the received string. |
53 Function responsible to return the Hash value for the received string. |
57 |
54 |
58 @internalComponent |
55 @internalComponent |
59 @released |
56 @released |
60 |
57 |
61 @param aString - String on which Hash value calcualtion to be done |
58 @param aString - const string& on which Hash value calcualtion to be done |
62 */ |
59 */ |
63 int HashTable::Hash(String aString) |
60 int HashTable::Hash(const string& aString) { |
64 { |
|
65 unsigned int hashVal = 0; |
61 unsigned int hashVal = 0; |
66 int length = aString.length(); |
62 int length = aString.length() ; |
67 /* we start our hash out at 0 */ |
63 /* we start our hash out at 0 */ |
68 |
64 |
69 /* for each character, we multiply the old hash by 31 and add the current |
65 /* for each character, we multiply the old hash by 31 and add the current |
70 * character. Remember that shifting a number left is equivalent to |
66 * character. Remember that shifting a number left is equivalent to |
71 * multiplying it by 2 raised to the number of places shifted. So we |
67 * multiplying it by 2 raised to the number of places shifted. So we |
72 * are in effect multiplying hashval by 32 and then subtracting hashval. |
68 * are in effect multiplying hashval by 32 and then subtracting hashval. |
73 * Why do we do this? Because shifting and subtraction are much more |
69 * Why do we do this? Because shifting and subtraction are much more |
74 * efficient operations than multiplication. |
70 * efficient operations than multiplication. |
75 */ |
71 */ |
76 for(int strIter = 0; strIter < length ; strIter++) |
72 for(int strIter = 0; strIter < length ; strIter++) { |
77 { |
|
78 hashVal = aString[strIter] + (hashVal << 5) - hashVal; |
73 hashVal = aString[strIter] + (hashVal << 5) - hashVal; |
79 } |
74 } |
80 /* we then return the hash value mod the hashtable size so that it will |
75 /* we then return the hash value mod the hashtable size so that it will |
81 * fit into the necessary range |
76 * fit into the necessary range |
82 */ |
77 */ |
83 return hashVal % iSize; |
78 return hashVal % iSize; |
84 |
79 |
85 } |
80 } |
86 |
81 |
87 /** |
82 /** |
88 Function returns ture or false based on the String availability in Hash |
83 Function returns ture or false based on the string availability in Hash |
89 |
84 |
90 @internalComponent |
85 @internalComponent |
91 @released |
86 @released |
92 |
87 |
93 @param aString - String which needs to be searched |
88 @param aString - const char* which needs to be searched |
94 */ |
89 */ |
95 bool HashTable::IsAvailable(String aString) |
90 bool HashTable::IsAvailable(const string& aString) { |
96 { |
|
97 unsigned int hashVal = Hash(aString); |
91 unsigned int hashVal = Hash(aString); |
98 if (iTable[hashVal].size() > 0) |
92 if (iTable.count(hashVal) > 0) { |
99 { |
93 pair<Table::iterator,Table::iterator> range = iTable.equal_range(hashVal); |
100 StringList nameList = iTable[hashVal]; |
94 for(Table::iterator it = range.first; it != range.second ; it++) { |
101 StringList::iterator listIter = nameList.begin(); |
95 if(aString == it->second ) { |
102 while(listIter != nameList.end()) |
|
103 { |
|
104 if ((*listIter) == aString) |
|
105 { |
|
106 return true; |
96 return true; |
107 } |
97 } |
108 ++listIter; |
|
109 } |
98 } |
110 } |
99 } |
111 return false; |
100 return false; |
112 } |
101 } |
113 |
102 |
114 /** |
103 /** |
115 Function responsible to insert a single string into Hash table |
104 Function responsible to insert a single string into Hash table |
116 |
105 |
117 @internalComponent |
106 @internalComponent |
118 @released |
107 @released |
119 |
108 |
120 @param aString - String which needs to be inserted |
109 @param aString - const char* which needs to be inserted |
121 */ |
110 */ |
122 void HashTable::Insert(String aString) |
111 void HashTable::Insert(const string& aString) { |
123 { |
|
124 unsigned int hashVal = Hash(aString); |
112 unsigned int hashVal = Hash(aString); |
125 if(!IsAvailable(aString)) //Is exists |
113 if(!IsAvailable(aString)) { |
126 { |
114 iTable.insert(pair<unsigned int,string>(hashVal,aString)); |
127 iTable[hashVal].push_back(aString); |
|
128 } |
115 } |
129 } |
116 } |
130 |
117 |
131 /** |
118 /** |
132 Function responsible to insert list of strings into Hash table |
119 Function responsible to insert list of StringList into Hash table |
133 |
120 |
134 @internalComponent |
121 @internalComponent |
135 @released |
122 @released |
136 |
123 |
137 @param aString - String which needs to be inserted |
124 @param aString - string which needs to be inserted |
138 */ |
125 */ |
139 void HashTable::InsertStringList(StringList& aList) |
126 void HashTable::InsertStringList(const StringList& aList) { |
140 { |
127 for(StringList::const_iterator it = aList.begin(); it != aList.end(); it++ ) { |
141 StringList::iterator beginIter = aList.begin(); |
128 Insert(*it); |
142 StringList::iterator endIter = aList.end(); |
|
143 while(beginIter != endIter) |
|
144 { |
|
145 Insert((*beginIter)); |
|
146 ++beginIter; |
|
147 } |
129 } |
148 } |
130 } |
149 |
131 |
150 /** |
132 /** |
151 Function to delete an entry from Hash |
133 Function to delete an entry from Hash |
152 |
134 |
153 @internalComponent |
135 @internalComponent |
154 @released |
136 @released |
155 |
137 |
156 @param aString - String which needs to be deleted |
138 @param aString - const char* which needs to be deleted |
157 */ |
139 */ |
158 void HashTable::Delete(String aString) |
140 void HashTable::Delete(const string& aString) { |
159 { |
|
160 unsigned int hashVal = Hash(aString); |
141 unsigned int hashVal = Hash(aString); |
161 if(iTable[hashVal].size() > 0) |
142 if (iTable.count(hashVal) > 0) { |
162 { |
143 pair<Table::iterator,Table::iterator> range = iTable.equal_range(hashVal); |
163 StringList list = iTable[hashVal]; |
144 for(Table::iterator it = range.first; it != range.second ; it++) { |
164 StringList::iterator beginIter = list.begin(); |
145 if(aString == it->second ) { |
165 StringList::iterator endIter = list.end(); |
146 iTable.erase(it); |
166 while(beginIter != endIter) |
147 return ; |
167 { |
148 } |
168 if((*beginIter) == aString) |
|
169 { |
|
170 list.erase(beginIter); |
|
171 iTable[hashVal] = list; |
|
172 return; |
|
173 } |
|
174 ++beginIter; |
|
175 } |
149 } |
176 } |
150 } |
177 } |
151 } |