Detailed interpretation of tab[i = (n - 1) & hash]

tab[i = (n - 1) & hash] A detailed interpretation of

n representative tab The capacity of the array 16 -1（ Array subscript index from 0 Start ）
there hash Is a hash(key) Calculated

First, click and operate (&), Is to convert two operands into 2 Base number , according to 1 1 = 0 ,1 0 = 0, 0 0 = 0 Calculate according to the rules of

According to the data of the above procedure , To do the analysis

Current hash：2080,n = 16

(n - 1) & hash = 15 & 2080

Imagine biting and manipulation 1 1 Only then 1, and 15 The binary number of is 0000 0000 0000 1111 front 12 Position as 0 I don't need to see it anymore , No matter 2080 Binary number of 0000 1000 0010 0000 front 12 What is the number of bits , Before the final result 12 Bits are for 0

tab[i = (n - 1) & hash] The design of the , To ensure the i The value is [0,15] In this closed interval

There is another important reason , Namely （n-1）& hash = hash % n , The premise of satisfying this equation is ,n Must be 2 Of a Power

Why? ？

because 2 Of n The power of 10 The base number is converted to 2 Hexadecimal number , There is only one 1, The rest are 0, for instance 16（ Decimal system ）= 10000（ Binary system ）

16 = 2^4 Convert to 2 After base n=4 The first one is 1, That is to say 10000, And the front 15 It's through 16-1 Yes, I did , That is to say 10000-1 obtain 01111, At this time will be 2080 Convert to 2 Into the system for 0000 1000 0010 0000, And 01111 Do bit and operation , The final result is 2080%16 = 0

summary When a number satisfies m = 2^n be a % m = a & （m-1）

Many friends here will ask , Why do that ？

First 2 The hexadecimal operation must be faster than the remainder operation , Second, whether it's HashSet,LinkHashSet Maintenance of table The capacity of is 2^n Fang , It also guarantees （n-1）& hash The rationality of design

The above content is only for personal interpretation , If there is any misunderstanding , Please comment on , thank you