extendible hashing

Preface

First, what is an extensible hash (Extendible Hashing)?
We usually use hash It's all static hash, For example, a number wants to be deposited into hash In the table , Go first hash function , Then save it into the corresponding hash In the table , Pay attention to this hash The table is a static , Its size is fixed at the beginning of creation , As we store more and more data ,hash The watch is getting slower and slower , The conflict rate is also increasing , We'd better maintain hash The number of elements in the table accounts for hash 70% of the capacity of the meter , In this way, the conflict rate can be kept low , At this point, we use dynamic hash, That is, our extensibility hash

Scalable hash structure

Scalable hash Yes 2 Kinds of structure , Namely

• directory: Is an extensible array , Each array element stores a bucket The pointer to ,directory Each element has a unique id, This id interesting , Is a binary number
• bucket: As long as this is hash All the watches , Used to store hash Table data , In other words, more than one bucket form hash surface
• global depth: This thing and directory It matters , because directory Each array element of the has a unique id, This id It's binary bit Composition e.g 1,11,011, and global depth On behalf of you directory id There is one bit, Like our global depth by 3, So it corresponds to directory id At most 111, explain directory id At most 7, That is to say, at most 8 Array elements
• local depth: and global almost , however local depth It's corresponding to bucket,local depth Always less than or equal to global depth

About bucket, When one bucket The number of elements in exceeds the specified number , here bucket There will be divisions (bucket splitting)
About Directory, When bucket Split up ,directory It will happen expansion

Scalable hash The process of

Our traditional static hash The process is hash Function directly stores the value in the corresponding bucket, But in extensibility hash in , First pass through hash The function is stored in Directory in , Again by directory Pointing to corresponding bucket, The specific process is as follows

1. To be analyzed hash Of key The type of , May be int, May be string, May be float wait , Suppose our key Namely int Type digital 49

2. take key Convert to binary form ,49 Convert to binary to 110001

3. check global depth , hypothesis global depth by 3

4. Select corresponding directory, How to choose ？ our 49 Binary for 110001 altogether 6 position , and global depth by 3, It only needs 3 position , At this point we intercept 110001 The last three 001 As directory id

5. Start positioning to the corresponding bucket in

6. Start inserting elements , Again check bucket whether overflow
   7. If overflow, And Corresponding bucket Of local depth be equal to global depth Add one to all , And then again hash overflow Of bucket

   Be careful global depth Adding one will add a lot of elements , At this point, we need to point these extra array elements to local depth Less than global depth Of bucket On

   8. If overflow And the corresponding bucket Of loacl depth Greater than global depth, Only the corresponding bucket Of local depth Add one and re hash This overflow Of bucket that will do

Reference from ¹

---

1. https://www.geeksforgeeks.org/extendible-hashing-dynamic-approach-to-dbms/ ︎