Skip to content
Hallway
0:00 / 0:00

#hashtable#hashfunction#collisionresolution

Hash Tables and Hash Functions

Computer Science Lessons

254K subscribers • 1 video on Hallway

YouTube
  • Recommended by 2 people: 2 in engineering communities.

Beginner. No background in the topic needed.

1.7M views9 years ago2 recommendations

Computer scienceData structuresAlgorithms

An explanation of hash table fundamentals, hash algorithms, and collision resolution techniques like probing and chaining.

This computer science video describes the fundamental principles of the hash table data structure which allows for very fast insertion and retrieval of data. It covers commonly used hash algorithms for numeric and alphanumeric keys and summarises the objectives of a good hash function. Collision resolution is described, including open addressing techniques such as linear and quadratic probing, and closed addressing techniques such as chaining with a linked list.

Why it's here

2 people recommend this

What people say. Recommended as a good primer on hash tables and how they handle collisions.

u/DistilledProblemsin r/C_Programming • Recommends

On “How to hash in c?”

Without external libraries, you need to implement it yourself. Also, as an exercise, storing it as an unencrypted hash is fine, but never use this as actual security. This video is a good primer. However, you will need a slightly more sophisticated hash function since a password can contain both letters, numbers and special symbols.
4View on Reddit

u/roadelouin r/C_Programming • Recommends

On “How do memory writes happen, and what are the roles of the CPU & cache in writing to memory?”

Hey, You are kind of right. It would be a bit difficult to explain with text why hash tables don't need to be sparse, but fortunately there are great free resources available online for that. See [video for instance, it has some nice graphical illustrations. The issue in this very application comes from the fact that the requirements of the application make it so that normal data structure hypothesis might not hold anymore. Typically, one would assume that writing to an array is slightly faster than writing to a hashtable. But if the array is so large that it is often being swapped between cache levels, then that assumption might not hold anymore. In all honesty, trying to tell which im…
3View on Reddit

u/DistilledProblemsin r/C_Programming • Mentions

Did I correctly create a hash map? Sorry, this is yet another hash table post, but it's an important data structure so I guess it's justified. Is this correctly implemented? I basically just followed the algorithm in this video, using linear probing to insert data. #include <stdio.h> #define MAX 10 int main() { int i, j; char keysMAX = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'}; int hash_tableMAX; int valsMAX = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}; //keysi maps to valsi int ASCIIMAX; //buffer for ASCII values for keys int positionsMAX; for(i = 0; i < MAX; i++) { //fills hash table with "empty" el…
2View on Reddit