Data Structures: Hash Tables
Why Stack Overflow recommends it
Stack Overflow users link it when explaining how hash maps and dictionaries map keys to indexes and deal with collisions, often as a quick implementation overview.
Recommended by 1 people across 1 different months, 2018 to 2021.
What it is
A short HackerRank tutorial that introduces hash tables, covering how keys are hashed into array indexes and how collisions are handled. It is part of the Cracking the Coding Interview series presented by Gayle Laakmann McDowell and aimed at interview prep.
What people said
Recommends Shivangi Shandilya · 2021-09 · Stack Overflow · on “What is a hash map in programming and where can it be used”
Hash maps saves a lot of time as compared to other search criteria. We have a hash key that corresponds to a hash code which further helps to find its index value. In terms of implementation, hash maps takes a string converts it into an integer and remaps it to convert it into an index of an array which helps to find the required value. To go in detail we can look for handling collisions in hash maps. Like instead of using array we can go with the linked list. There is a short video available to understand it. Available here : Implementation example --> [this video] Sample: int hashCode(String s) { logic }
Cites mfaani · 2018-05 · Stack Overflow · on “How to handle hash collisions for Dictionaries in Swift”
From what I've learned from here [this video] . Dictionaries are stored in an 2 dimension array. Where each key is appended to the inner array at the outer array's _index_ of `key's hashValue % array.count`. I guess it's not actually stored in an array, but that's what you're asked to do at an interview...
Cites kabirbaidhya · 2020-09 · Stack Overflow · on “Big O of Finding the Intersection in two Unsorted Arrays Using filter() in JavaScript”
The above function has a time complexity of O(M * N) . But can you make this solution more efficient? Yes. You can reduce it to O(M + N) . TLDR: Use a hash table to achieve linear time complexity O(M + N). Approach 1 Check every elements of array 1 with every element of array 2. (This is the approach you're using.) function findCommonElem(arr1, arr2) { return arr1.filter(x => arr2.includes(x)); } const arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const arr2 = [2, 4, 6, 8, 10, 12, 14, 16, 20]; console.log(findCommonElem(arr1, arr2)); // [2, 4, 6, 8, 10]; Time complexity = O(M * N) Every element from array 1 is checked with every element of array 2 at the worst case. So, it's M * N. Space compexity