Please enable JavaScript.

Coggle requires JavaScript to display documents.

Compression and encryption - Coggle Diagram

- - - - Linear probing
        
        Linear probing - for small data sets with empty indices in the hash table. As the table fills, the effectiveness of search algorithms decreases. The algorithm has to look at entire clusters of entries to see if its target is among them. This 'clustering' of values with many collisions slows searches down.
        When a key creates a hash value that references a position that is already occupied, you must place the data in the next free position in the hash table. You can probe sequentially or use an interval until an empty bucket is found.
        Retrieving data (linear probing)
        When there has been a collision, data will not be in the correct place. Process for retrieving data from a hash table where collisions have been dealt with by linear probing is as follows:
        
        hash the key to generate the index value
        
        examine indexed position to see if the key matches the key of the data you are looking for
        
        if there is no match, check each location that follows until the matching record is found
        
        if you reach an empty bucket without finding a matching key, the data is not in the hash table.
        This can reduce the efficiency of using a hash table for searching. You might have to inspect every position of the array until you find the data you are looking for. It is important to design your hash table to have extra capacity; hopefully your algorithm will find a free position not too far from the correct place.
      - Chaining
        
        Chaining/closed addressing
        Each index in the hash table contains a linked list of values.
        When a new data item arrives, it is added to the end of the linked list at the appropriate index location.
        These will collide with the items already there. Using the chaining method, they are added to the end of the linked lists at those locations, in the order they arrive.
        The linked lists grow and shrink as items are added and removed from the hash table, depending on the collisions that take place.
        Instead of storing the actual data in the hash table, you store a pointer to a location where the data is stored. Each data item is stored as a node with three attributes:
        
        the key value
        
        the data
        
        a pointer to the next node
        
        First value to be stored will have a Null pointer as it is the only item in the list. When there is a collision, the pointer for the first node at that location will be updated to point to the new node, creating a chain of nodes whose keys resolve to the same hash value.
        Retrieving data (chaining)
        When collisions have been dealt with using chaining, the data will always be accessed through a single location in the hash table. The process for retrieving it is as follows:
        
        hash the key to generate the index value
        
        examine indexed position to get the pointer to the node at the head of the list
        
        examine key of the node to see if it matches the key of the data you are looking for
        
        if it is not the node you are looking for, follow the linked list until you find the node you are looking for
        
        if you reach the end of the list without finding a matching key or the head pointer was null, the data is not in the hash table
        
        Where every key hashes to the same value, you could end up carrying out a linear search. It is important that your hash function is designed and tested to minimise the number of possible collisions.
    - - The two methods of collisions have their pros and cons.
        
        Memory efficiency
        Chaining has to assign memory 'buffers' to each linked list, it doesn't know how much space it will need to store data items.
        If a list runs out of memory space and another item arrives, it causes an 'overflow' error and data is lost. If most of the linked lists remain empty, this makes chaining memory-inefficient.
        
        Linear probing makes efficient use of memory as each index requires space for only a single item.
        
        Search efficiency
        Linear probing is efficient for sparsely-filled hash tables, with few collisions and plenty of room to put them. Becomes less efficient as the hash table fills and collisions force it to put data farther from the correct index.
        
        Chaining is efficient for densely-filled hash tables with potential collisions. Search algorithm needs to check the contents of a single index.
        
        Algorithm efficiency
        Search algorithms for hash tables that use chaining are complicated to write than for those that use linear probing.
        
        Linear probing is the more efficient method to use for sparsely-populated hash tables. Chaining is the more efficient method to use for densely-populated hash tables.