C++ Hash Table Implementation

Показать описание

A tutorial on implementing a hash table in C++ via separate chaining.

Рекомендации по теме

Комментарии

Man! You are just amazing! I have coding interviews in a few days, and you just saved my ass. You have implemented almost all DS, and they are so neat and clean, the way it should be! Thanks man!

Mmmmmkoogfssdvbhvggg

love the perfection. the way you type and your explanation

soniasingh

Thank you!! This was so helpful. Supplementing my classes with your videos now - my teacher only reads from the book.

strawberrysultan

Very useful and clear video, thank you for helping me understand hash tables better.

nadiequintero

Thanks guy! Very nice tutorial. Here's my go at the search function:
string HashTable::searchTable(int key) {
int hashValue = hashFunction(key);
auto& cell = table[hashValue];
auto bItr = begin(cell);
bool keyExists = false;

for (; bItr != end(cell); bItr++) {
if (bItr->first == key) {
keyExists = true;
return bItr->second;
}
}

if (!keyExists)
return "Result Not Found";
}

panicineurope

super amazing work man, props! you're a great programmer and teacher.

MrJQd

This was incredibly helpful. You explain each step clearly which is hard to find! Thank you:)

luceracox

isEmpty can be implemented in a better way (O(1) as opposed to O(hashGroups)), You could create a variable that stores number of empty hashGroups. So, numEmptyHashGroups = hashGroups initially. On insert, decrement numEmptyHashGroups if it is the first node in the list. Similarly when removing the item, increment numEmptyHashGroups if it is the last value. Implementation of isEmpty will become as simple as numEmptyHashGroups == hashGrorups. Also, in current implementation you don't need to calculate the sum, you could just return false if at any point the list is not empty. Aggregating the sum can cause overflow.

jasmeetsingh

in isEmpty, you dont need a sum. Just return true whenever the size is non zero in the loop, it will on average save a lot of execution time

nnewram

thanks a lot. But I think using C sytle array is bad practice. The books always say use vector:
I mean instead of this: list<pair<int, string>> table[hashGroups];

isn't this better ? : using listType = list<pair<int, string>>;
vector<listType, hashGroups> table;

Maybe, I am wrong, what do you think ?

halily.

The keyboard sounds like asmr. relaxing..

rohitk

thanks for helping me write my first working hash function. test on this tomorrow in 12 hours...

miclaymon

That was a neat explanantion!
thanks a lot, man!

franky

Thank you, this was quite helpful, and quite catchy too XD. Keep up the good work, and all the very best

adnanlokhandwala

Great video! Especially in covering effective collision handling, since not all tutorials do that very well. FWIW, 1:25 should be "what it looks like" or just "how it looks". "Like" sounds a bit redundant if you pair it with "How". One of the best tutorials on this topic in any case.

grayscale-bitmask