DEV Community

How does a Map work?

Jan van Brügge on April 04, 2018

Sometimes, as a developer, you want to store key-value pairs. For example you may want to access a user object by its username. The best suited d...
Read full post
Collapse
 
pchinery profile image
Philip •

Hi Jan,

thank you for sharing yours insight here :)

I would just like to add that the map implementation you have shown (which of course is a very simple one) is not O(1) for insert and lookup, as it might iterate the whole list whole finding a spot. This approach also requires a lot of work when removing items, as you have to fill gaps that might arise. But with a good hash function, maps of course can have an average case order of one, as collisions are rare compared to the number of items already in the map.

Philip

Collapse
 
jvanbruegge profile image
Jan van Brügge •

Yeah, linear hashing is a simple but rather weak avoidance strategy.

Collapse
 
notriddle profile image
Michael "notriddle" Howell •

Hashing is also not the only common implementation of an abstract map. There's also variants on the binary search tree.

class TreeMap<Value> {
  private root: TreeMapNode<Value>?;
  public insert(key: number, value: Value) {
    if (root === undefined) {
      root = new TreeMapNode(key, value);
    } else {
      root.insert(key, value);
    }
  }
  public get(key: number): Value {
    if (root === undefined) {
      return undefined;
    } else {
      return root.get(key);
    }
  }
}
class TreeMapNode<Value> {
  private key: number;
  private value: Value;
  private less: TreeMapNode<Value>?;
  private greater: TreeMapNode<Value>?;
  constructor(key: number, value: Value) {
    this.key = key;
    this.value = value;
  }
  public function insert(key: number, value: Value) {
    if (this.key === key) {
      this.value = value;
    } else if (this.key < key) {
      if (this.less === undefined) {
        this.less = new TreeMapNode(key, value);
      } else {
        this.less.insert(key, value);
      }
    } else if (this.key > key) {
      if (this.greater === undefined) {
        this.greater = new TreeMapNode(key, value);
      } else {
        this.greater.insert(key, value);
      }
    } else {
      throw new Exception("key may not be NaN");
    }
  }
  public function get(key: number): Value {
    if (this.key === key) {
      return this.value;
    } else if (this.key < key) {
      if (this.less === undefined) {
        return undefined;
      } else {
        return this.less.get(key);
      }
    } else if (this.key > key) {
      if (this.greater === undefined) {
        return undefined;
      } else {
        return this.greater.get(key);
      }
    } else {
      throw new Exception("key may not be NaN");
    }
  }
}

The above implementation sucks, by the way. I don't think it's valid TypeScript, and it isn't self-balancing so it has average-case O(log n) lookup and worst-case O(n) lookup.

Collapse
 
jvanbruegge profile image
Jan van Brügge •

Yeah, Haskell uses balanced binary trees for example