hash tables remember that we've specified an array with twice as many cells as data items thusperhaps half the cells are empty one approachwhen collision occursis to search the array in some systematic way for an empty cell and insert the new item thereinstead of at the index specified by the hash function this approach is called open addressing if cats hashes to , but this location is already occupied by parsnipthen we might try to insert cats in , for example second approach (mentioned earlieris to create an array that consists of linked lists of words instead of the words themselves thenwhen collision occursthe new item is simply inserted in the list at that index this is called separate chaining in the balance of this we'll discuss open addressing and separate chainingand then return to the question of hash functions so far we've focused on hashing strings this is realisticbecause many hash tables are used for storing strings howevermany other hash tables hold numbersas in our employee-number example in the discussion that followsand in the workshop appletswe use numbers--rather than strings--as keys this makes things easier to understand and simplifies the programming examples keep in mindhoweverthat in many situations these numbers would be derived from strings open addressing in open addressingwhen data item can' be placed at the index calculated by the hash functionanother location in the array is sought we'll explore three methods of open addressingwhich vary in the method used to find the next vacant cell these methods are linear probingquadratic probingand double hashing linear probing in linear probing we search sequentially for vacant cells if , is occupied when we try to insert data item therewe go to , then , and so onincrementing the index until we find an empty cell this is called linear probing because it steps sequentially along the line of cells the hash workshop applet the hash workshop applet demonstrates linear probing when you start this appletyou'll see screen similar to figure in this applet the range of keys runs from to the initial size of the array is the hash function has to squeeze the range of keys down to match the array size it does this with the modulo operator (%)as we've seen beforearrayindex key arraysize