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.
Hashing is also not the only common implementation of an abstract map. There's also variants on the binary search tree.
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