This content originally appeared on DEV Community and was authored by Code_Regina
-Intro to Hash Tables
-Handling Collisions
-Hash Table Keys and Values
Intro to Hash Tables
Hash tables are used to store key-value pairs.
They are similar to arrays but there is no required order.
Hash tables have a great speed so they are widely used.
Hash tables have different names in other languages but the functionality is the same.
Python hash tables are called dictionaries.
JavaScript hash tables are called objects and maps.
function hash(key, arrayLen) {
let total = 0;
for (let char of key) {
// map "a" to 1, "b" to 2, "c" to 3, etc.
let value = char.charCodeAt(0) - 96
total = (total + value) % arrayLen;
}
return total;
}
Handling Collisions
There are two ways to handle hash table collisions.
- Separate Chaining
- Linear Probing
Separate Chaining
is when the hash table has each index in the array has stored values with more data similar to an array or a linked list.
Linear Probing
When a collision is found, a search is performed throughout the array to find the next empty slot.
Hash Table Keys and Values
Keys - Loops through the hash table array and returns an array of keys in the table
Values - Loops through the hash table array and returns an array of values in the table
keys(){
let keysArr = [];
for(let i = 0; i < this.keyMap.length; i++){
if(this.keyMap[i]){
for(let j = 0; j < this.keyMap[i].length; j++){
if(!keysArr.includes(this.keyMap[i][j][0])){
keysArr.push(this.keyMap[i][j][0])
}
}
}
}
return keysArr;
}
values(){
let valuesArr = [];
for(let i = 0; i < this.keyMap.length; i++){
if(this.keyMap[i]){
for(let j = 0; j < this.keyMap[i].length; j++){
if(!valuesArr.includes(this.keyMap[i][j][1])){
valuesArr.push(this.keyMap[i][j][1])
}
}
This content originally appeared on DEV Community and was authored by Code_Regina
Code_Regina | Sciencx (2021-10-31T18:52:13+00:00) Hash Tables. Retrieved from https://www.scien.cx/2021/10/31/hash-tables/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.