Before you keep reading...
Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.
Before you keep reading...
Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.
- binary search¶
search method in which one repeatedly divides a sorted data structure in half and determines if the item is in one half of it until the item is found or deemed not in the data.
a method of collision resolution in which each slot in a hash table holds a reference to a collection of items
a conflict of having two or more items sharing the same slot in a hash table
- collision resolution¶
a systematic method for resolving hash table collisions
items being mapped in a hash table near each other because of collisions and linear probing resulting in items with collisions being put together
- folding method¶
a method for constructing a hash function by dividing the item into equally sized pieces and then adding the pieces together to get a hash value. The value is then divided by the size of the hash table and the remainder becomes the slot for that item.
generating a value given an input that can be used to find the input by searching for the value.
- hash function¶
the mapping between an item and its slot in a hash table
- hash table¶
a collection of items which are stored in such a away as to make it easy to find them
- linear probing¶
an open addressing technique in which each slot is visited one at a time systematically
- load factor¶
Represents how full a hash table is. Its the number of items in a hash table divided by the size of the table.
an associate data type that stores key-data pairs
- mid-square method¶
a method for constructing a hash function by squaring the item and then using some portion of the result.
- open addressing¶
a collision resolution that tries to find the next open slot/address in the hash table
- perfect hash function¶
a hash function that maps each item to a unique hash slot
- quadratic probing¶
a variation of linear probing in which rehashing is done using successive squared values
putting an item into a hash table after a collision
the algorithmic process of finding a particular item in a collection of items
- sequential search¶
search method in which one follows the underlying ordering of items in a collection of data to find a specific item
a position in a hash table