Flashcards
SCC 201 - Hashing
Cards in this deck (41)
- 1What is a hash function?A hash function h is applied to a particular field called the hash field to obtain address of disk block containing record
– If hash field is also a key field
it is referred to as the hash key - 2Advantages of hash function?For most records a single-block access is needed to retrieve record.
– Search for record within block
can be carried out in main memory buffer
• (+ve): Very fast access under certain search conditions - 3Why is internal hashing used?• Used as an internal search structure within a program a group of records is accessed exclusively by using value of one field
• Implemented as a hash table using an array of records - 4What does h(K) = K mod M return?– Returns remainder of integer hash field value K after division by M
– Remember, M is number of slots in table, so...
Operation ensures h(K) returns value
in range 0 to M-1 - 5What is the function h(K) used for after hashing?The value, h(K), is used as the address for the record
Operation ensures h(k) return value in range 0 to M-1 - 6What happens to non-integer hash fields after operations?– Non-integer hash field can be transformed to integer before application of hash function
- 7Another hashing function is folding? What is foldingApply...
· Arithmetic function such as addition, or
· Logical function such as exclusive OR
...to different portions of hash field values to calculate hash address - 8Another alternative to folding to calculate hash addresses?Simply pick some digits of hash field value,
for example, 3rd, 5th and 7th to form hash address - 9What could happen i internal hashing due to hash field space being larger than address space?A collision could occur in the address space.
- 10Two ways to resolve collision in internal hashing?Open addressing
Multiple hashing
chaining - 11How does open addressing work?• Proceed from occupied position specified by hash, check subsequent positions in order ...until an unused position is found
- 12How does multiple hashing work?Apply a second hash function if first results in a collision
• If another collision results use open addressing or, apply a third hash function
...and then use open addressing if necessary - 13How does chaining work?Chaining involves storing a overflow pointer which points to a memory space containing the remaining data to the stored pointer.
- 14What is external hashing for and what is it's target address space made of and describe it?This is hashing for disk files
• Target address space is made of buckets
– A bucket is either one disk block or a cluster of contiguous disk blocks
– Each bucket holds multiple records - 15How does external hashing work?Hashing function maps a key into a relative bucket number
– It does not assign an absolute block address to bucket
– A bucket table maintained in file header converts bucket number into a corresponding disk block address - 16What stores pointer to bock containing related records?bucket table in file header stores pointer
to block containing related records. - 17Why are collisions less severe in buckets and what possibility do we have to entertain?• As many records as will fit, many can hash to same bucket
– We have to entertain possibility that :
buckets will fill to capacity and new records might be hashed to buckets that are already full - 18How to solve collisions using buckets?– We can use a variation of chaining
- 19What information does the record ptr store?Record ptr includes both block address
and relative record position within block - 20What happens when we delete a record from a bucket and the bucket has an overflow chain?– Remove record from its bucket
– If bucket has an overflow chain, we can move one of overflow records into main bucket.
– If record to be deleted is already in overflow, simply remove it from linked list - 21What does record deletion in extensible hashing require you to keep track of?Requires keeping track of empty overflow
locations - 22Disadvantages of extensible hashing?Searching for record using non-hash field is as expensive as for an unordered file
Modifying hash field requires moving record to different bucket
– This requires deletion of old record
and insertion of modified record - 23If M = number of buckets for address space and m = maximum number of records that can fit in one bucket, what is the maximum number of records that fit in an allocated space?Maximum number of records that fit in
allocated space = m * M - 24Why is external hashing scheme described has static?A fixed number of buckets M is allocated
- 25What happens if number of records is substantially less than m*M?– Substantially less than m * M, we are left with a lot of unused space
- 26What happens if number of records is substantially larger than m*M?– Substantially larger than m * M, there will be a large number of collisions
-> long linked lists for overflow - 27Benefits of dynamic hashing to static hashing?Easier to expand or shrink file dynamically
(as compared to static hashing) - 28What fact does dynamic hashing take advantage of?Takes advantage of the fact:
Result of applying a hash function
is a non-negative integer
It can be represented as a binary number - 29What is dynamic hashing access structure built on?Access structure built on binary representation of hashing function result
– This is a string of bits
– Called the hash value of a record - 30How are records distributed to buckets in dynamic hashing?Records distributed to buckets
based on leading bits in their hash values - 31State one form of dynamic hashing?One form of dynamic hashing is extendible
hashing - 32Using M in hash scheme ties us to fixed and static size of M buckets. Why is this a problem?– Does not cope well with dynamic files
- 33Disadvantage of record distribution?Expensive
- 34What is a directory in relation to extendible hashing?– An array of 2d bucket addresses
– d is global depth - 35How is the directory entry determined and what determines how it's stored?• Integer value corresponding to higher order d bits of hash value used as index into array to determine directory entry
Address in entry determines bucket in which corresponding records are stored - 36Complete this statement Several directory entries with same first d’ bits may contain what? What happens to records that hash to this location?– Several directory entries with same first d’ bits may contain same bucket address
- Does not have to be a distinct bucket
for each of the 2d directory entries
Records that hash to these locations fit in a single bucket - 37what is d' and where is it stored?d’ is the local depth
– Stored with each bucket
– Number of bits on which bucket contents are based - 38What happens to the value of d when it's expanded or shrinked?– Value of d can be increased or decreased by one at a time.
- 39What happens to the number of entries in directory array when it's expanded or shrinked?In former case, number of entries in directory array is doubled, while in the latter, it is halved
– Doubling is needed if bucket with d’ = d overflows
– Halving is needed if (possibly after some deletions) d > d’ for all buckets - 40Advantages of extendible hashing?(+ve): Performance does not degrade as file grows
– In static hashing,
collisions increase and overflow chains become large
• (+ve): No space is allocated for future growth
– Additional buckets can be allocated dynamically
• (+ve): Space overhead for the directory is negligible
– Maximum directory size is 2k
where k is number of bits in hash value
(+ve): Splitting causes minor reorganisation in most cases
– Only records in one bucket are redistributed to two new buckets - 41Disadvantages of extendible hashing?, include it's effect on overall performance?(–ve): Reorganisation is expensive when
directory has to be doubled or halved
• (–ve): Two block accesses required
– Directory must be searched before accessing the buckets
Overall performance penalty is minor
– Desirable choice for dynamic files
Information
- Description
- Flashcards on SCC 201 - Hashing, created by Ayo Olutobi on 24/03/2017.
- Created by
- Ayo Olutobi
- Views
- 0
- Rating