This benchmark is created with a Index where the String value was about 300 characters long using a single thread on a 2.4GHz Intel CPU and a rather slow 5200 RPM HDD. The output shows very clear that you should not fill a hashtable anywhere near the capacity and the results of doing so isn't strange at all: the entities will then need to share the same position in the hashtable and will thus require navigating the list of entites in order to be inserted or read. Thus I suspect peaking insert values are due to random keys with hash codes that cluster large amount of entities at the same position in the hashtable. Capacity 8 times greater than number of items: capacity items random write ms/item sequencial read ms/items random read ms/item 8000 1000 0.225 0.119 0.093 12000 1500 0.208 0.102 0.085 18000 2250 0.382 0.091 0.238 27000 3375 0.243 0.095 0.128 40496 5062 0.282 0.103 0.149 60744 7593 0.322 0.098 0.173 91112 11389 0.284 0.104 0.133 136664 17083 0.555 0.116 0.226 204992 25624 0.731 0.106 0.244 307488 38436 1.015 0.077 0.252 461232 57654 0.798 0.093 0.165 691848 86481 2.449 0.071 0.298 1037768 129721 0.493 0.115 0.090 1556648 194581 2.515 0.089 0.167 2334968 291871 1.788 0.073 0.121 3502448 437806 0.834 0.088 0.085 Capacity equal to number of items: capacity items random write ms/item sequencial read ms/items random read ms/item 1000 1000 0.32 0.0902 0.164 1500 1500 0.409 0.0747 0.263 2250 2250 2.324 0.0675 1.682 3375 3375 0.774 0.0695 0.620 5062 5062 1.030 0.0684 0.818 7593 7593 1.736 0.0706 1.030 11389 11389 1.311 0.0692 0.582 17083 17083 3.106 0.0707 1.277 25624 25624 4.646 0.0712 1.418 38436 38436 6.903 0.0657 1.511 57654 57654 5.118 0.0664 0.822 86481 86481 14.944 0.0647 1.660 129721 129721 1.605 0.0861 0.169 And then I gave up waiting.. The numbers are however rather linear if you compare capacity. The test was made using class o.a.l.b.hashtable.Benchmark kalle@apache.org capacity items random write ms/item sequencial read ms/items random read ms/item 8000 1000 0.805 0.1293 0.15842 12000 1500 0.683 0.11794 0.15646 18000 2250 0.877 0.09969 0.33615 27000 3375 0.691 0.10393 0.21926 40496 5062 0.786 0.1072 0.25094 60744 7593 0.724 0.09941 0.3041 91112 11389 0.817 0.12546 0.31408 136664 17083 1.065 0.09652 0.48662 204992 25624 1.145 0.12075 0.72948 307488 38436 1.560 0.10247 0.92083 461232 57654 1.223 0.09537 0.61455 691848 86481 2.614 0.11821 1.35132 1037768 129721 1.004 9.79918 0.32858 1556648 194581 2.991 2.49016 0.98731 2334968 291871 2.382 4.32559 0.58027 3502448 437806 1.338 5.19182 0.27377