Untitled
unknown
plain_text
a year ago
3.9 kB
6
Indexable
/** * Create a hash table of Person records based on given relations. * @precondition All ids appearing in relations are in the people list. * @param people peoples ids and names * @param relations parent-child relations * @return Returns a hash table with a Person record for each person from people * that includes all relationships according relations. */ export function toHashtable(people: People, relations: Relations): PersonTable { // 1. convert to new format People & Relations -> Person /* People: list(pair(id1, name1), pair(id2, name2)) */ function convertValues(people, relations){ } //information lagras i hashtablen som [key, value] (UTGÅNGSPUNKT) function createHashTable(size) { const hashTable = new Array(size); function hashMethod(key) { //identity hash function return key; } //probing function här; FÖR SET: insertar om null ELLER undefined // för get: tillåter null, inte undefined function setKey(key, value) { //values kmr från den array som skapats när ingångsvärdena har processerats key = person.id, value = person function probeForSet(key) { let index = hashMethod(key) % size; let startIndex = index; while (hashTable[index] !== undefined && hashTable[index]!== null) { index = (index + 1) % size; if (index === startIndex) { return -1; // table is full } } return index; } const indexToSetAt = probeForSet(key); if (indexToSetAt === -1) { return 'Error: Hash table is full.' } hashTable[indexToSetAt] = [key, value]; //key = person.id, value = person object } //usage: setKey(person.id, person); => placed in hash table at (probed) index function getKey(key) { function probeForGet(key) { let index = hashMethod(key) % size; let startIndex = index; while (hashTable[index][0] !== key) { //hanterar null implicit if (hashTable[index] === undefined) { return 'Error: Key not found or deleted'; } index = (index + 1) % size; // if (index === startIndex) { // return -1; // table is full // } } return index; } //probing function här; fail om UNDEFINED påträffas (standard vid skapandet av hashtablen), så betyder det att keyn inte finns. Om keyn har probats vid set, så kommer indexet som getats inte vara undefined; kmr antingen innehålla key eller null } // function deleteKey(key) { function probeForDel(key) { let index = hashMethod(key) % size; let startIndex = index; while (hashTable[index][0] !== key) { //hanterar null implicit if (hashTable[index] === undefined) { //hanterar undefined return 'Error: Key not found or deleted'; } index = (index + 1) % size; if (index === startIndex) { //hanterar om ej funnen; ej undefined return -1; // table is full } } return index; } const keyToDel = probeForDel(key); if (keyToDel === -1){ return 'Error: Key not found or deleted.' } hashTable[keyToDel] = null; return console.log("Key" + keyToDel + "deleted.") //if key != key //när key är hittad -> hashTable[key] = null; //probing function här; VIKTIGT med NULL ist. för undefined(?) } } createHashTable(300000000000); // 0. Persons + Relations -> personTable (~array) // 1. hash identity function // 2. hash functions: get, set, delete // 3. implement BCE, etc.
Editor is loading...
Leave a Comment