Hashing

Description

Mind Map on Hashing, created by WillJ on 05/01/2014.
WillJ
Mind Map by WillJ, updated more than 1 year ago
WillJ
Created by WillJ about 11 years ago
25
1

Resource summary

Hashing
  1. Hash Function:Is a function H, applied to a key k, which generates a hash value H(k) of range smaller than the domain of values of k.
    1. Hash Value: is the value generated by the application of the hash function to the key. This value can be used as the hash table index where the key and any associated data can be stored if this table location is free
      1. Hash Table: The table gets it's name from the method used to determine the row to use. The hash value generated by applying the has function to the key is the table index where the record should be stored if the row is free.
        1. Hash Key: the key that the hash function is applied to
          1. Hashing: The process of applying a hash function to a key to generate a hash value
            1. Collision: A collision occurs when two or more different keys hash to the same has value.
              1. Open Hashing: Method in which a collision is resolved by storing the record in the "next available" location
                1. Closed Hashing: In a collision the other rows of the hash table are closed to the colliding record which must, instead, be attached to the table slot in a chain or linked list of other colliding records. The table slat uses a pointer field to point to the linked list.
                  1. Rehashing: The key is hashed again because the initial hash has resulted in a collision. One method of rehashing is to keep trying the next location and so on (modulo length of table) until a free slot is found in which to store the record.
                    1. Linear Rehash: The original hash value is incremented by 1 modulo N, then 2 modulo N, then 3 modulo N and so on until an empty slot is found in the table of size N rows.
                      Show full summary Hide full summary

                      Similar

                      Hash Functions
                      msladey
                      Static Perfect Hashing
                      msladey
                      Cuckoo Hashing
                      msladey
                      'The Merchant of Venice' - William Shakespeare
                      cian.buckley
                      Weimar Germany 1919: The Spartacists and the constitution
                      Chris Clayton
                      Cory & Manuel
                      Prudensiano Manu
                      Spanish Subjunctive
                      MrAbels
                      An Inspector Calls -- Themes
                      Sadia Aktar
                      5 Tips for motivating your students
                      Jen Molte
                      An Inspector Calls Revision Notes
                      Noor Sohail
                      Salem does not remember
                      Salma Moustafa