λ Hash set open-hashing

======= Algorithm ======= <syntax js> /** * Creates a new HashSet. * @constructor * @param {number} [capacity=10] - The initial capacity of the set. */ function HashSet(capacity) { this.array = Array(typeof capacity === "number"? capacity : 10); } HashSet.prototype = { /** Inserts numeric/string `data` into this hash set. */ insert: function(data) { // Hash the data to get a slot. var slot = this.hashData(data); // Insert the data into that slot. if (!this.array[slot]) { this.array[slot] = new LinkedList(); } this.array[slot].insertOrderedUnique(data); }, /** Removes `data` from this hash set. */ remove: function(data) { // Hash the data to get a slot. var slot = this.hashData(data); // Remove the data from that slot. if (this.array[slot]) { this.array[slot].remove(data); } }, /** Hash `data` with respect to its type to get a slot. */ hashData: function(data) { var dataHash; if (typeof data === "number") { dataHash = data; } else if (typeof data === "string") { dataHash = fnv1aHashString(data); } else { throw "Unsupported type (not string/number) in HashSet." } return Math.floor(Math.abs(dataHash))%this.array.length; } } </syntax> ======= Support ======= <syntax js> hash = new HashSet(10); function preRun() { if (!(hash instanceof HashSet)) { // Copy the hash from data - used for web-workers. var myhash = new HashSet(10); myhash.array = hash.array; for (var i=0;i<hash.array.length;i++) { if (myhash.array[i] && !(myhash.array[i] instanceof LinkedList)) { myhash.array[i] = new LinkedList(); myhash.array[i].first = hash.array[i].first; } } // Replace the global 'hash' with the converted one. hash = myhash; } } LinkedList.prototype.length = function() { var lengthNode = function(node) { if (!node) { return 0; } else { return 1 + lengthNode(node.next); } } return lengthNode(this.first); } LinkedList.prototype.insertOrderedUnique = function(data) { var insertOrderedUniqueNode = function(node, data) { if (!node || data < node.data) { node = new LinkedList.Node(data, node); } else if (data !== node.data) { node.next = insertOrderedUniqueNode(node.next, data); } return node; } this.first = insertOrderedUniqueNode(this.first, data); } LinkedList.prototype.forEach = function(callback) { var n = this.first; while (n) { callback(n.data); n = n.next; } }</syntax> ======= Tests ======= <syntax js> function insertRandom(hash) { // Insert 10 random numbers and 10 strings var toInsert = []; for (var i=0; i<10; i++) { toInsert.push(Math.random()*100); // a number toInsert.push(""+Math.random()*100); // a string } for (var i=0; i<toInsert.length; i++) { hash.insert(toInsert[i]); } return toInsert; } function testInsertion() { var hash = new HashSet(10); var inserted = insertRandom(hash); // Enumerate all stored data and remove it from toInsert. hash.forEach(function (d) { var idx = inserted.indexOf(d); if (idx >= 0) { inserted.splice(idx, 1); } else { throw "Invalid item in hash set: "+d; } }); assert(inserted.length === 0, "Not all items in hash set."); } function testRemove() { var hash = new HashSet(10); var inserted = insertRandom(hash); for (var i=0; i<inserted.length; i++) { hash.remove(inserted[i]); } var count = 0; hash.forEach(function (d) { count++; }); assert(count === 0, "Set should have nothing in it."); }</syntax> ======= Options ======= <syntax js> { "title": "Hash set open-hashing", "height": "570px", "preRunSource": true, "persistentGlobals": ["hash"], "import": ["fowler_noll_vo_hash-string", "linked-list", "hash_set-open_hashing-foreach"] }</syntax> ======= Visualisation ======= <syntax html> <html> <head> <script src="algorithms-lib/d3.v3.min.js"></script> <script src="algorithms-lib/list.js"></script> <link rel="stylesheet" type="text/css" href="algorithms-lib/list.css"/> <style type='text/css'> input { width: 50px; } svg { font-family: Verdana, Helvetica; font-size: 12px; } </style> <script> function setup() { svg = d3.select("#result") .append("svg") .attr("width", 348) .attr("height", 400) .append("g").attr("transform", "translate(20.5,20.5)"); returnText = svg.append("text") .attr("dx", "0") .attr("dy", "40"); listVis = new ListVisualisation(svg); } var poppedMarker = {}; function globals() { // Return a unique marker that enables to identify when popped has not been set. return {"popped": poppedMarker}; } var nodeIndex = 0; function idNode(node) { if (!node.hasOwnProperty("id")) { node.id = nodeIndex++; } } function updateD3(x, clean, duration) { var hash = x.lookupInScope("hash"); var selectedSlot = x.lookupInScope("slot"); if (typeof selectedSlot !== "number" && x.returnedFrom === x.lookupInScope("HashSet").prototype.hashData) { selectedSlot = x.returnedValue; } // Create lists. listVis.nodesToDisplay = []; for (var i=0;i<hash.array.length;i++) { var list = hash.array[i]; if (list) { // Copy in list. var nodes = []; var x = 60; var n = list.first; while (n) { n.x = x; x += 60; n.y = i*32+1; idNode(n); listVis.nodesToDisplay.push(n); n = n.next; } } } listVis.pointersToDisplay = []; for (var i=0;i<hash.array.length;i++) { listVis.pointersToDisplay.push({x:0, y:32*i, w:32, h:32, id:i, value:hash.array[i]? hash.array[i].first : null}); } listVis.update(duration); // Highlight selected slot. svg.selectAll(".ptr") .attr("id", function(d,i) {return i;}) .classed("selected", function(d, i) {return i === selectedSlot;}); // Move it to the front. var use = svg.select("#list-data").select("use"); if (use.empty()) { use = svg.select("#list-data").append("use"); } // Not sure why but without this check Safari makes the use node go black. use.attr("xlink:href", "#"+selectedSlot); } function update(n, x, isRunning, duration) { // Update the d3 visualisation. updateD3(x, false, duration); document.getElementById("addButton").disabled = isRunning; document.getElementById("removeButton").disabled = isRunning; } function data() { var data = parseFloat(document.getElementById('input').value); if (isNaN(data)) data = '"'+document.getElementById('input').value+'"'; return data; } function insert() { runScript("hash.insert("+ data() +")"); } function insertLots() { runScript("for(var i=0;i<10;i++) {hash.insert((Math.random()*100)|0);}"); } function removeItem() { runScript("hash.remove("+ data() +")"); } window.onload = function() { setup(); }; </script> </head> <body style="height:480px"> <button id="addButton" onclick="insertLots()">Insert Lots</button><button id="addButton" onclick="insert()">Insert</button><button id="removeButton" onclick="removeItem()">Remove</button> <input id="input" value="7"><br><br> <div id=result> </div> </body> </html></syntax>