re: How does a Map work? VIEW POST

FULL DISCUSSION
 

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.

 

Yeah, Haskell uses balanced binary trees for example

code of conduct - report abuse