General Idea Purpose:Design a kind of tables that can perform insertions,deletions,and finds in constant average time. In this chapter,we discuss the Hash table ADT. The ideal hash table data structure is merely an array of some fixed size,containing the keys. Typically,a key is a string with an associated value (for instance,salary information)
General Idea ◼ Purpose: Design a kind of tables that can perform insertions, deletions, and finds in constant average time. ◼ In this chapter, we discuss the Hash table ADT. ◼ The ideal hash table data structure is merely an array of some fixed size, containing the keys. ◼ Typically, a key is a string with an associated value (for instance, salary information)
General Idea The implementation of hash tab/es is frequently called hashing. We will refer to the table size as Tab/eSize. The common convention is to have the table run from 0 to Tab/eSize-1
General Idea ◼ The implementation of hash tables is frequently called hashing. ◼ We will refer to the table size as TableSize. ◼ The common convention is to have the table run from 0 to TableSize-1
General Idea Each key is mapped into some number in the range 0 to Tab/eSize-1 and placed in the appropriate cell. ■ The mapping is called a hash function,which ideally should be simple to compute and should ensure that any two distinct keys get different cells. ■ Since there are a finite number of cells and a virtually inexhaustible supply of keys,this is clearly impossible, and thus we seek a hash function that distributes the keys evenly among the cells
General Idea ◼ Each key is mapped into some number in the range 0 to TableSize-1 and placed in the appropriate cell. ◼ The mapping is called a hash function, which ideally should be simple to compute and should ensure that any two distinct keys get different cells. ◼ Since there are a finite number of cells and a virtually inexhaustible supply of keys, this is clearly impossible, and thus we seek a hash function that distributes the keys evenly among the cells
General Idea 0 1 John 25000 2 3 Phil 45000 4 5 6 Dave 15000 7Mary35000 ■ The only remaining problems deal with choosing a function,deciding what to do when two keys hash to the same value (this is known as a collision),and deciding on the table size
General Idea ◼ The only remaining problems deal with choosing a function, deciding what to do when two keys hash to the same value (this is known as a collision), and deciding on the table size. 0 1 John 25000 2 3 Phil 45000 4 5 6 Dave 15000 7 Mary 35000
Hash Function If the input keys are integers,when simply returning (Key mod Tab/eSize)is generally a reasonable strategy,unless Key happens to have some undesirable properties. In this case,the choice of hash function needs to be carefully considered. For instance,if the table size is 10 and the keys all end in zero,then the standard hash function is a bad choice
Hash Function ◼ If the input keys are integers, when simply returning (Key mod TableSize) is generally a reasonable strategy, unless Key happens to have some undesirable properties. ◼ In this case, the choice of hash function needs to be carefully considered. ◼ For instance, if the table size is 10 and the keys all end in zero, then the standard hash function is a bad choice