34825556
Description
Flashcards by Malachy Moran-Tun, updated more than 1 year ago
|
|
Created by Malachy Moran-Tun
over 2 years ago
|
|
| Question | Answer |
| What is Hashing and when is it Used? | > Creates an index value to be used instead of linear searches > Used for large collections of data that have to be accessed quickly (without looking through all the records) > Uses a hashing algorithm to calculate said index values > A hash table stores the data in the correct index value calculated by the hashing algorithm |
| How do most Hashing Algorithms Work? | Index Number = Sum of Values* mod Size of Array *this could be the sum of ASCII codes, or just the sum of digits in a number etc. |
| How do you Search for an Item in a Hash Table? | > Apply the hashing algorithm to find the index value > Check the resulting element in the table > If the item is there, return it > If the cell is empty, the item is not in the table > If there is another item in the same spot, keep moving forwards until found or there is a blank cell |
| What is the Folding Method? | > Hashing algorithm > Splits the item into equal parts and adds them together to give a value > The modulo of the value and the size of the array is the index e.g., 123456 = 12 + 34 + 56 = 102 102 % 100 = 2 |
| What are Collisions? | > Two pieces of data have the same value (known as synonyms) > Becomes more common as the hash table fills up, so the size of the table needs to be considered when making it |
| What is Rehashing? | > Finds an empty slot when a collision has occurred > Most basic is known as "linear probing" (goes to the next blank cell) > This can lead to clustering, where positions around common collision values are filled > Prevents some items from being stored in their proper location |
| How do you Reduce Collisions in Hash Tables? | > Use a larger table > Instead of using a rehashing algorithm, use a linked list as a 2D array, known as chaining |
| What are Dictionaries? | > word book by big brains or alternatively > Abstract data type consisting of associated pairs of items > Uses a hash table to implement them - a key and a value (key:value) e.g., = {342:"AAAA", 634:"hello there"} |
| What Operations can be Performed on Dictionaries? | > Create a new dictionary > Add a new key:value pair > Delete a key:value pair > Amend the value in a key:value pair > Return the value associated with the key > Return true or false, depending on if a value is present in the dictionary > Return the length of the dictionary, i.e., the number of key:value pairs |
Want to create your own Flashcards for free with GoConqr? Learn more.