A very common data structure in Java is java.util.HashMap. The advantage of such a data structure is fast, but more importantly, convenient data access since only a key, which can be any sort of Java object, has to be provided to obtain the value; again, any type of Java object is supported as the key. While convenient for the programmer, java.util.HashMap has some drawbacks. The most important are:

• Memory overhead due to usage of objects as keys and values
• Very cache-unfriendly memory layout
• Impossible to directly address fields by calculating offsets

This means that simple but important things, such as sequential scans, result in very random and cache-unfriendly memory access patterns. Therefore, Tungsten has introduced a new data structure called BytesToBytesMap, which has improved the memory locality and has led to less space overhead by avoiding the usage of heavyweight Java objects, which has improved performance. Sequential scans are very cache friendly, since they access the memory in sequence.