Managing collisions

Managing Collisions

Managing Collisions

As a DSP handling big data and high request rate (as well as in any busy and complex server) we find it useful to keep in-memory mappings for data we use on request basis. Typically these mappings are stored in hashmap data structures, whose performance is highly influenced by the data distribution inside its buckets, or put differently, by the number of collisions.

A second use-case of interest which also involves collisions is when we try to map a set of N unique ids into a new domain of size B, in an attempt to reduce the space used for storing ids in internal data structures and data stores.

In both cases collisions should be taken into account. In the case of a hashmap we are dealing with a trade-off between memory consumption and running time. A larger table means faster lookups/updates, but slower iteration and greater memory consumption. In the mapping scenario, we may be saving space by reducing the id signature size, but on the same time we are losing data due to collisions. In both cases we would like to be able to control the number of collisions, keeping them below some predefined threshold.

private static void analyze(HashMap<?,?> m) throws ReflectiveOperationException {
      Map.Entry<?,?>[] entries = getTable(m);
      System.out.println("Bins: " + entries.length);
      System.out.println("Items: " + m.size());
      Field nextField = getNextField(entries);
      int collisions = 0;
      for (Map.Entry<?,?> e : entries) {
        if (e != null) {
          Object next = e;
          while ((next = nextField.get(next)) != null) {
      System.out.println("Collisions: " + collisions);
    private static Map.Entry<?, ?>[] getTable(Map<?, ?> map) throws ReflectiveOperationException {
      Field tableField = map.getClass().getDeclaredField("table");
      return (Map.Entry<?, ?>[]) tableField.get(map);
    private static Field getNextField(Map.Entry<?,?>[] mapTable) throws ReflectiveOperationException {
      Class<?> nodeType = mapTable.getClass().getComponentType();
      Field nextNodeField = nodeType.getDeclaredField("next");
      return nextNodeField;

Let’s try it on a HashMap with many random strings as keys. Internally, HashMap uses powers of 2 for table sizes.

If we want to have a saturated map with 2^20=1,048,576 bins, we need to insert 0.75*1,048,576 = 786432 items:

public static void main(String[] args) throws ReflectiveOperationException {
      final int N = 786_432;
      HashMap<String, Void> m = new HashMap<>();
      for (int i = 0; i < N; i++) {
        m.put(UUID.randomUUID().toString(), null);
Logo Polaris

Want to look
under the hood?

Enter Ubimo. With its unique model, Ubimo has disrupted the traditional way of media-buying by offering tech companies and advertisers alike an all-inclusive platform designed with the buyer’s best interest in mind. Hence why I’m writing to you today, to tell you what I love about Ubimo’s platform – and why it’s here to stay.

Eyal Schneider
Eyal Schneider

Lead Engineer

Share on linkedin
Share on twitter
Share on facebook
Why DTC companies love OOH
Articles & Research

Why DTC Companies Love Out-of-Home Advertising

Many DTC brands recognize the benefits of OOH, using it heavily as part of their media strategies. Get the full report!

martech award 2019 best use of ai

Ubimo Wins “Best Use of Artificial Intelligence in MarTech” from the 2019 MarTech Breakthrough Awards Program

Prestigious Annual Awards Program Recognizes Ubimo’s Groundbreaking Use of AI for the Out-of-Home Industry

Get the latest in
Location Intelligence

Subscribe to the blog

dtc for ooh a ubimo q&a
Articles & Research

DTC for OOH – A Q&A with Jeremy Flynn, CCOA

We sat down with Jeremy Flynn from Clear Channel Outdoor Americas to talk about the incredible value out-of-home has to offer direct-to-consumer brands.

Ins and Outs of DOOH
Articles & Research

The Ins and Outs of DOOH

DOOH is a small but rapidly growing slice of the advertising media pie, and an increasingly important part of an effective omnichannel marketing plan. Check out the full report.

lunch break
Articles & Research

What do people really do during their lunch breaks?

Ubimo’s Polaris technology uncovers the many lunchtime habits across workplaces […]