1 | /* |
2 | * Copyright 2004-2014 H2 Group. Multiple-Licensed under the MPL 2.0, |
3 | * and the EPL 1.0 (http://h2database.com/html/license.html). |
4 | * Initial Developer: H2 Group |
5 | */ |
6 | package org.h2.util; |
7 | |
8 | |
9 | /** |
10 | * The base for other hash classes. |
11 | */ |
12 | public abstract class HashBase { |
13 | |
14 | /** |
15 | * The maximum load, in percent. |
16 | * declared as long so we do long arithmetic so we don't overflow. |
17 | */ |
18 | private static final long MAX_LOAD = 90; |
19 | |
20 | /** |
21 | * The bit mask to get the index from the hash code. |
22 | */ |
23 | protected int mask; |
24 | |
25 | /** |
26 | * The number of slots in the table. |
27 | */ |
28 | protected int len; |
29 | |
30 | /** |
31 | * The number of occupied slots, excluding the zero key (if any). |
32 | */ |
33 | protected int size; |
34 | |
35 | /** |
36 | * The number of deleted slots. |
37 | */ |
38 | protected int deletedCount; |
39 | |
40 | /** |
41 | * The level. The number of slots is 2 ^ level. |
42 | */ |
43 | protected int level; |
44 | |
45 | /** |
46 | * Whether the zero key is used. |
47 | */ |
48 | protected boolean zeroKey; |
49 | |
50 | private int maxSize, minSize, maxDeleted; |
51 | |
52 | public HashBase() { |
53 | reset(2); |
54 | } |
55 | |
56 | /** |
57 | * Increase the size of the underlying table and re-distribute the elements. |
58 | * |
59 | * @param newLevel the new level |
60 | */ |
61 | protected abstract void rehash(int newLevel); |
62 | |
63 | /** |
64 | * Get the size of the map. |
65 | * |
66 | * @return the size |
67 | */ |
68 | public int size() { |
69 | return size + (zeroKey ? 1 : 0); |
70 | } |
71 | |
72 | /** |
73 | * Check the size before adding an entry. This method resizes the map if |
74 | * required. |
75 | */ |
76 | void checkSizePut() { |
77 | if (deletedCount > size) { |
78 | rehash(level); |
79 | } |
80 | if (size + deletedCount >= maxSize) { |
81 | rehash(level + 1); |
82 | } |
83 | } |
84 | |
85 | /** |
86 | * Check the size before removing an entry. This method resizes the map if |
87 | * required. |
88 | */ |
89 | protected void checkSizeRemove() { |
90 | if (size < minSize && level > 0) { |
91 | rehash(level - 1); |
92 | } else if (deletedCount > maxDeleted) { |
93 | rehash(level); |
94 | } |
95 | } |
96 | |
97 | /** |
98 | * Clear the map and reset the level to the specified value. |
99 | * |
100 | * @param newLevel the new level |
101 | */ |
102 | protected void reset(int newLevel) { |
103 | // can't exceed 30 or we will generate a negative value |
104 | // for the "len" field |
105 | if (newLevel > 30) { |
106 | throw new IllegalStateException("exceeded max size of hash table"); |
107 | } |
108 | size = 0; |
109 | level = newLevel; |
110 | len = 2 << level; |
111 | mask = len - 1; |
112 | minSize = (int) ((1 << level) * MAX_LOAD / 100); |
113 | maxSize = (int) (len * MAX_LOAD / 100); |
114 | deletedCount = 0; |
115 | maxDeleted = 20 + len / 2; |
116 | } |
117 | |
118 | /** |
119 | * Calculate the index for this hash code. |
120 | * |
121 | * @param hash the hash code |
122 | * @return the index |
123 | */ |
124 | protected int getIndex(int hash) { |
125 | return hash & mask; |
126 | } |
127 | |
128 | } |