Flashcards
Hash Tables and Dictionaries | Data Structures - OCR Computer Science A Level
Cards in this deck (9)
- 1What 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 - 2How 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. - 3How 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 - 4What 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 - 5What 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 - 6What 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 - 7How 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 - 8What 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"} - 9What 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
Information
- Description
- A level Computer Science (Data Structures) Flashcards on Hash Tables and Dictionaries | Data Structures - OCR Computer Science A Level, created by Malachy Moran-Tun on 05/12/2021.
- Created by
- Malachy Moran-Tun
- Views
- 12
- Rating