6 ms·
Totally pedantic, but no HashMap.get function is O(1). In order do a look-up, you have to compute the hash, whose size is at least log2(n).
by rand_r 10y ago
Totally pedantic, but no HashMap.get function is O(1). In order do a look-up, you have to compute the hash, whose size is at least log2(n).
- conjectures 10y agoNot being funny, I actually don't know: Is the n in log2(n) the size of thing you're hashing? AFAIK the O(1) statement is referring to how many things you have hashed.
- rand_r 10y agoIn context, n is the number of things in the hashmap. You need log2(n) bits per item to store n unique items. So the hash function is operating on an input of log2(n) bits. There's no way the hash function takes less than log2(n) time to work on log2(n) bits of input.
- lkitching 10y agoYou don't need hash codes to be unique for items in the table so there doesn't need to be any relation between the size of the hash and the size of the table. The time taken by the hash function depends on the size of the keys not the size of the table.
- to3m 10y agoIf the cost of a hash function is related to anything, it is more usually the number of bits in the input.
- FT_intern 10y agoI've always used the assumption that objects have pre-calculated/stored hashes
- dahart 10y agoThe reason hash computation is traditionally called constant time is because it doesn't change while the hash table grows. Big O describes how run time or memory consumption grows as input grows, and with a hash table, the hash computation typically does not grow. Calling a hash table O(log2(N)) gets misleading when you measure a hash function's performance, and it doesn't change as the table grows. So you're right about your technicality, but you're using big-O slightly differently than how everyone else is using it. The implications are interesting, in that if the hash computation did grow as O(log2(N)), then it would (theoretically) outperform the current typical O(1) hash table implementation, and they would meet only when the table is full. Another way to see O(1) is that hash computation is always implemented not as a log2(N) function, but is log2(MAX_N), where MAX_N is the size of a full table, and since MAX_N is a constant, the complexity is O(1). A side note is that not all hash tables are implemented using an array that can hold N items. Some hash tables use linked lists instead of re-hashing for collisions, meaning that your array can be arbitrarily less than N in size, meaning that it is definitely possible to have a hash function that takes less than log2(MAX_N) time. In that case, insertion time becomes explicitly greater than O(1).
- bogomipz 10y agoI'm not following your logic here: "The implications are interesting, in that if the hash computation did grow as O(log2(N)), then it would (theoretically) outperform the current typical O(1) hash table implementation, and they would meet only when the table is full." How would O(log n) ever out perform constant time, O(1)? Could you elaborate?
- dahart 10y agoThis is and always has been an important part of understanding what big-O notation actually means. O(1) means constant time, it does not tell you what the constant is. The constant can be large. In this case, if your hash always takes 64 bit values and always produces 64 bit values, it is O(1). If your hash were O(log2(N)), then your hash function with an empty table would do 1 bit worth of work, and would do only one operation. But when the table grew to contain 1,000 elements, it would do 10 bits worth of work. The O(log2(N)) algorithm with N < 2^64 is always faster (in theory) than the O(1) algorithm that does a constant 64 bits of work. The O(1) algorithm pays off in spades for N >> 2^64, it will become much faster than the logarithmic one, but for small N, log(N) is smaller than 64.
- deleted 10y ago[deleted]