Great job on making a reproducible example.
My first concern is that linkedList does not appear to be a clean abstraction. Let's consider the C++ class std::unordered_map, which has a similar approach to The Odin Project:
- A bucket is a (doubly) linked list of key-value pairs.
- A hash table stores an array of buckets (resized on rehashing), the number of buckets, and the total number of elements (inserted key-value pairs).
It makes use of three abstractions:
- The (doubly) linked list needs traversal, data insertion (
insert), and node deletion (erase).
- The bucket needs
insert to achieve update-or-insertion (upsert) by key (returning whether the linked list grew due to not finding a key), delete to achieve deletion-or-nothing (remove) by key (returning whether the linked list shrank due to finding a key), and traversal to achieve value access (access) by key (returning the value). For all of the above, it needs to find a node by key.
- The hash table needs to
hash keys to corresponding buckets for access and keep a running count of element sizes by observing the return values of upsert and remove. If the number of elements divided by the number of buckets exceeds the load factor, it needs to rehash appropriately.
The code above doesn't quite work with these layers (although all abstractions leak somewhat). The data structure resembles a linked list, but find should be for buckets and size should be counted by hash tables. I don't think tail is necessary - if anything, insertion at the front rather than the back would take better advantage of temporal locality (more recently inserted values are more likely to be accessed).
The repeated use of traverse (recursive) is confusing to me and I think it can be made much simpler. Here is my best attempt at the bucket level:
function bucket() {
let head = null; // [key, value, next, prev]
// returns the first node with a key or null
function find(key) {
let node = head;
while (node != null) {
if (node.key == key)
return node;
node = node.next;
}
return null;
}
// updates or inserts the key / value,
// returning whether insertion was needed
function upsert(key, value) {
let node = find(key);
// not found? insert at front
if (node == null) {
const new_node = {
key: key,
value: value,
next: head,
prev: null
};
if (head != null)
head.prev = new_node;
head = new_node;
return true;
}
node.value = value;
return false;
}
// deletes all nodes with a key,
// returning whether deletion was needed
function remove(key) {
let node = find(key);
// not found? do nothing
if (node == null)
return false;
if (node.prev == null)
head = head.next;
else
node.prev.next = node.next;
if (node.next != null)
node.next.prev = node.prev;
return true;
}
// returns the value at key or other if not found
function access(key, other) {
let node = find(key);
if (node == null)
return other;
return node.value;
}
// prints in string form
function toString() {
if (head == null)
return '{}';
let result = '{\n';
let node = head;
while (node != null) {
result += ` ${node.key}: ${node.value}\n`;
node = node.next;
}
return result + '}';
}
return {
upsert,
remove,
access,
toString
};
}
And here are some tests:
const test_list = bucket();
let insert = test_list.upsert(2, 'x');
console.log('test_list[2] = "x"', insert);
console.log(test_list.toString());
insert = test_list.upsert(5, 140);
console.log('test_list[5] = 140', insert);
console.log(test_list.toString());
insert = test_list.upsert(4, 'hi!');
console.log('test_list[4] = "hi"', insert);
console.log(test_list.toString());
insert = test_list.upsert(4, 'hello!');
console.log('test_list[4] = "hello!"', insert);
console.log(test_list.toString());
insert = test_list.upsert(5, test_list.access(5, 0) + 1);
console.log('test_list[5] += 1', insert);
console.log(test_list.toString());
insert = test_list.upsert(16, test_list.access(16, 0) + 1);
console.log('test_list[16] += 1', insert);
console.log(test_list.toString());
insert = test_list.upsert(80, test_list.access(80, "") + "a");
console.log('test_list[80] += "a"', insert);
console.log(test_list.toString());
let shrink = test_list.remove("abc");
console.log('test_list.remove("abc")', shrink);
console.log(test_list.toString());
shrink = test_list.remove(80);
console.log('test_list.remove(80)', shrink);
console.log(test_list.toString());
shrink = test_list.remove(4);
console.log('test_list.remove(4)', shrink);
console.log(test_list.toString());
shrink = test_list.remove(16);
console.log('test_list.remove(16)', shrink);
console.log(test_list.toString());
shrink = test_list.remove(2);
console.log('test_list.remove(2)', shrink);
console.log(test_list.toString());
shrink = test_list.remove(5);
console.log('test_list.remove(5)', shrink);
console.log(test_list.toString());
shrink = test_list.remove(5);
console.log('test_list.remove(5)', shrink);
console.log(test_list.toString());
And here is a version separating the linked list / bucket functionality:
function doubly_linked_list() {
let head = null; // [data, next, prev]
// gets the head
function get_head() {
return head;
}
// front-inserts a node with data
function insert(data) {
const new_node = {
data: data,
next: head,
prev: null
};
if (head != null)
head.prev = new_node;
head = new_node;
}
// erases a node (assumed to be valid)
function erase(node) {
// update the prev node
if (node.prev == null)
head = head.next;
else
node.prev.next = node.next;
// update the next node
if (node.next != null)
node.next.prev = node.prev;
}
return {
get_head,
insert,
erase
};
}
function bucket() {
const data_list = doubly_linked_list();
// returns the first node with a key or null
function find(key) {
let node = data_list.get_head();
while (node != null) {
if (node.data.key == key)
return node;
node = node.next;
}
return null;
}
// updates or inserts the value for the given key,
// returning whether insertion was needed
function upsert(key, value) {
let node = find(key);
// not found? insert at front
if (node == null) {
data_list.insert({
key: key,
value: value
});
return true;
}
node.data.value = value;
return false;
}
// deletes all nodes with the given key,
// returning whether deletion was needed
function remove(key) {
let node = find(key);
// not found? do nothing
if (node == null)
return false;
data_list.erase(node);
return true;
}
// returns the value at key or other if not found
function access(key, other) {
let node = find(key);
if (node == null)
return other;
return node.data.value;
}
// prints in string form
function toString() {
const head = data_list.get_head();
if (head == null)
return '{}';
let result = '{\n';
let node = head;
while (node != null) {
result += ` ${node.data.key}: ${node.data.value}\n`;
node = node.next;
}
return result + '}';
}
return {
upsert,
remove,
access,
toString
};
}
Hope this helps!
