Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Copyright 2017, University of Freiburg,
- // Chair of Algorithms and Data Structures.
- // Author: Hannah Bast <bast@cs.uni-freiburg.de>,
- // Axel Lehmann <lehmann@cs.uni-freiburg.de>.
- // Marc Michel <marcmichel117@gmail.com>
- // NOTE: this is a code design suggestion in pseudo-code. It is not supposed to
- // be compilable in any language. You have to translate it to Python, Java or
- // C++ yourself. The purpose of this file is to suggest a basic design and
- // settle questions you might have on what exactly your code is supposed to do.
- // Implementation of a fixed-size HashMap, as explained in lecture 4a + 4b.
- // This hash map only allows strings as keys and integers as values. You may
- // assume, that the size of the hash table is given on initialization. For
- // collision resolution, you are allowed to use one of:
- // - open addressing ("offene Addressierung")
- // - seperate chaining ("Hashing mit Verkettung")
- // - cuckoo hashing ("Kuckuck Hashing") [Advanced!]
- package HashMap;
- import java.util.ArrayList;
- public class HashMap {
- public KeyValuePair[] hashMap;
- private int sizeOfMap;
- public static void main(String[] args){
- HashMap hash = new HashMap(10);
- hash.insert("marc",10);
- hash.insert("marc",11);
- KeyValuePair[] array = hash.getKeyValuePairs();
- for (int i = 0; i < array.length; i++) {
- System.out.println(array[i].getKey() + " " +array[i].getValue());
- }
- }
- /**
- * Constructor of the hashMap class.
- *
- * @param sizeOfMap
- */
- public HashMap(int sizeOfMap) {
- init(sizeOfMap);
- }
- /**
- * Check if there exists an entry with the given key in the hash table.
- * If such an entry exists, return its associated integer value.
- * Otherwise return -1.
- *
- * @param key
- * @return value if found else -1
- */
- public int lookup(String key) {
- int index = hashFunction(key);
- KeyValuePair root = hashMap[index];
- int result = searchLinkedList(key, root);
- return result;
- }
- /**
- * Insert the given key (given as a string) with the given value (given as
- * an integer). If the hash table already contains an entry for the given key,
- * update the value of this entry with the given value.
- *
- * @param key
- * @param value
- */
- public void insert(String key, int value) {
- int index = hashFunction(key);
- KeyValuePair root = hashMap[index];
- if (root == null) {
- hashMap[index] = new KeyValuePair(key, value);
- } else {
- searchAndAdd(hashMap[index], key, value);
- }
- }
- /**
- * Returns all elements in the array as a single list of pairs where key is the
- * first element and value the second.
- *
- * @return KeyValuePair[]
- */
- public KeyValuePair[] getKeyValuePairs() {
- ArrayList<KeyValuePair> arrayList = new ArrayList<>();
- for (int i = 0; i < sizeOfMap; i++) {
- KeyValuePair root = hashMap[i];
- if(root != null) {
- KeyValuePair next = root;
- while (next != null) {
- arrayList.add(next);
- next = next.getNext();
- }
- }
- }
- KeyValuePair[] array = new KeyValuePair[arrayList.size()];
- for (int i = 0; i < arrayList.size(); i++) {
- array[i] = arrayList.get(i);
- }
- return array;
- }
- /**
- * Calculates the index for the given key.
- *
- * @param key
- * @return index
- */
- private int hashFunction(String key) {
- return (getAsciiValue(key) % sizeOfMap);
- }
- /**
- * Returns the sum of the key. Therefor it adds the asciivalue of each letter in the key.
- *
- * @param key
- * @return sum
- */
- private int getAsciiValue(String key) {
- int result = 0;
- for (int i = 0; i < key.length(); i++) {
- char character = key.charAt(i);
- int asciiValue = (int) character;
- result += asciiValue;
- }
- return result;
- }
- private void searchAndAdd(KeyValuePair root, String key, int value) {
- if (root != null) {
- KeyValuePair next = root;
- boolean found = false;
- while (!found && next != null) {
- if (next.getKey() == key) {
- found = true;
- } else {
- next = next.getNext();
- }
- }
- if (found) {
- next.setValue(value);
- } else {
- hashMap[hashFunction(key)] = addToLinkedList(root, new KeyValuePair(key, value));
- }
- }
- }
- /**
- * Adds the linkedList to next.next and returns the new root.
- *
- * @param root
- * @param next
- * @return the new linkedList.
- */
- private KeyValuePair addToLinkedList(KeyValuePair root, KeyValuePair next) {
- next.setNext(root);
- return next;
- }
- /**
- * Search key in the given LinkedList.
- * @param key
- * @param root
- * @return -1 if key is not found or the value of the KeyValuePair.
- */
- private int searchLinkedList(String key, KeyValuePair root) {
- int value = -1;
- if (root != null) {
- KeyValuePair next = root;
- boolean found = false;
- while (!found && (next != null)) {
- if (next.getKey() == key) {
- value = next.getValue();
- found = true;
- } else {
- next = next.getNext();
- }
- }
- }
- return value;
- }
- /**
- * Initialise the hashMap.
- *
- * @param sizeOfMap
- */
- private void init(int sizeOfMap) {
- this.sizeOfMap = sizeOfMap;
- hashMap = new KeyValuePair[sizeOfMap];
- fillWithNull(sizeOfMap);
- }
- /**
- * Fills the array with null.
- *
- * @param sizeOfMap
- */
- private void fillWithNull(int sizeOfMap) {
- for (int i = 0; i < sizeOfMap; i++) {
- hashMap[i] = null;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement