cmccabe commented on a change in pull request #10334:
URL: https://github.com/apache/kafka/pull/10334#discussion_r596378196
##########
File path: metadata/src/main/java/org/apache/kafka/timeline/BaseHashTable.java
##########
@@ -56,12 +61,27 @@
this.elements = new Object[expectedSizeToCapacity(expectedSize)];
}
+ /**
+ * Calculate the capacity we should provision, given the expected size.
+ *
+ * Our capacity must always be a power of 2, and never less than 2.
+ */
static int expectedSizeToCapacity(int expectedSize) {
- if (expectedSize <= 1) {
- return 2;
+ if (expectedSize >= MAX_CAPACITY / 2) {
+ return MAX_CAPACITY;
+ }
+ return Math.max(MIN_CAPACITY, roundUpToPowerOfTwo(expectedSize * 2));
Review comment:
Hash tables are designed to always have some empty slots. The fraction
of slots that is allowed to be full is called the load factor. See
https://programming.guide/hash-table-load-factor-and-capacity.html .
Increasing the load factor will save memory, but lookup time will be degraded.
The standard Java load factor is 0.75, which is what we're trying to achieve
here.
Actually, looking at this again, we should technically be using 0.75 in the
initial expected sizing, rather than a load factor of 0.5 as it is doing now.
0.5 is more traditional but since the other expansion logic uses 0.75, best to
be consistent.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
