Java Reference
In-Depth Information
This is the same as
h(hashCode) = supplementalHash(hashCode) & (N -
1
)
since
N
is a value of the power of
2
.
27.2
What is a hash code? What is the hash code for
Byte
,
Short
,
Integer
, and
Character
?
27.3
How is the hash code for a
Float
object computed?
27.4
How is the hash code for a
Long
object computed?
27.5
How is the hash code for a
Double
object computed?
27.6
How is the hash code for a
String
object computed?
27.7
How is a hash code compressed to an integer representing the index in a hash table?
27.8
If
N
is a value of the power of
2
, is
N / 2
same as
N >> 1
?
27.9
If
N
is a value of the power of
2
, is
m % N
same as
m & (N - 1)
for any integer
m
?
✓
✓
Check
Point
A collision occurs when two keys are mapped to the same index in a hash table.
Generally, there are two ways for handling collisions: open addressing and separate
chaining.
Key
Point
Open addressing
is the process of finding an open location in the hash table in the event of
a collision. Open addressing has several variations:
linear probing
,
quadratic probing
, and
double hashing
.
open addressing
27.4.1 Linear Probing
When a collision occurs during the insertion of an entry to a hash table,
linear probing
finds
the next available location sequentially. For example, if a collision occurs at
hashTable[k %
N]
, check whether
hashTable[(k+1) % N]
is available. If not, check
hashTable[(k+2)
% N]
and so on, until an available cell is found, as shown in Figure 27.2.
add entry
linear probing
Note
When probing reaches the end of the table, it goes back to the beginning of the table.
Thus, the hash table is treated as if it were circular.
circular hash table
0
1
2
3
4
5
6
7
8
key: 44
For simplicity, only the keys are
shown and the values are not
shown. Here N is 11 and
index = key % N.
New element with
key 26 to be inserted
key: 4
key: 16
key: 28
Probe 3 times before
finding an empty
cell
9
10
key: 21
F
IGURE
27.2
Linear probing finds the next available location sequentially.
Search WWH ::
Custom Search