Advertisement
Guest User

Untitled

a guest
May 23rd, 2017
615
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.25 KB | None | 0 0
  1. // Copyright 2017, University of Freiburg,
  2. // Chair of Algorithms and Data Structures.
  3. // Author: Hannah Bast <bast@cs.uni-freiburg.de>,
  4. //         Axel Lehmann <lehmann@cs.uni-freiburg.de>.
  5. //         Marc Michel <marcmichel117@gmail.com>
  6.  
  7. // NOTE: this is a code design suggestion in pseudo-code. It is not supposed to
  8. // be compilable in any language. You have to translate it to Python, Java or
  9. // C++ yourself. The purpose of this file is to suggest a basic design and
  10. // settle questions you might have on what exactly your code is supposed to do.
  11.  
  12. // Implementation of a fixed-size HashMap, as explained in lecture 4a + 4b.
  13. // This hash map only allows strings as keys and integers as values. You may
  14. // assume, that the size of the hash table is given on initialization. For
  15. // collision resolution, you are allowed to use one of:
  16. // - open addressing ("offene Addressierung")
  17. // - seperate chaining ("Hashing mit Verkettung")
  18. // - cuckoo hashing ("Kuckuck Hashing") [Advanced!]
  19.  
  20. package HashMap;
  21.  
  22. import java.util.ArrayList;
  23.  
  24. public class HashMap {
  25.  
  26.     public KeyValuePair[] hashMap;
  27.     private int sizeOfMap;
  28.  
  29.     public static void main(String[] args){
  30.         HashMap hash = new HashMap(10);
  31.         hash.insert("marc",10);
  32.         hash.insert("marc",11);
  33.  
  34.         KeyValuePair[] array = hash.getKeyValuePairs();
  35.         for (int i = 0; i < array.length; i++) {
  36.             System.out.println(array[i].getKey() + " " +array[i].getValue());
  37.         }
  38.     }
  39.  
  40.     /**
  41.      * Constructor of the hashMap class.
  42.      *
  43.      * @param sizeOfMap
  44.      */
  45.     public HashMap(int sizeOfMap) {
  46.         init(sizeOfMap);
  47.     }
  48.  
  49.  
  50.     /**
  51.      * Check if there exists an entry with the given key in the hash table.
  52.      * If such an entry exists, return its associated integer value.
  53.      * Otherwise return -1.
  54.      *
  55.      * @param key
  56.      * @return value if found else -1
  57.      */
  58.     public int lookup(String key) {
  59.         int index = hashFunction(key);
  60.         KeyValuePair root = hashMap[index];
  61.         int result = searchLinkedList(key, root);
  62.         return result;
  63.     }
  64.  
  65.  
  66.     /**
  67.      * Insert the given key (given as a string) with the given value (given as
  68.      * an integer). If the hash table already contains an entry for the given key,
  69.      * update the value of this entry with the given value.
  70.      *
  71.      * @param key
  72.      * @param value
  73.      */
  74.     public void insert(String key, int value) {
  75.         int index = hashFunction(key);
  76.         KeyValuePair root = hashMap[index];
  77.  
  78.  
  79.         if (root == null) {
  80.             hashMap[index] = new KeyValuePair(key, value);
  81.         } else {
  82.             searchAndAdd(hashMap[index], key, value);
  83.         }
  84.     }
  85.  
  86.  
  87.     /**
  88.      * Returns all elements in the array as a single list of pairs where key is the
  89.      * first element and value the second.
  90.      *
  91.      * @return KeyValuePair[]
  92.      */
  93.     public KeyValuePair[] getKeyValuePairs() {
  94.         ArrayList<KeyValuePair> arrayList = new ArrayList<>();
  95.  
  96.         for (int i = 0; i < sizeOfMap; i++) {
  97.             KeyValuePair root = hashMap[i];
  98.             if(root != null) {
  99.                 KeyValuePair next = root;
  100.                 while (next != null) {
  101.                     arrayList.add(next);
  102.                     next = next.getNext();
  103.                 }
  104.             }
  105.         }
  106.  
  107.         KeyValuePair[] array = new KeyValuePair[arrayList.size()];
  108.         for (int i = 0; i < arrayList.size(); i++) {
  109.             array[i] = arrayList.get(i);
  110.         }
  111.         return array;
  112.     }
  113.  
  114.  
  115.     /**
  116.      * Calculates the index for the given key.
  117.      *
  118.      * @param key
  119.      * @return index
  120.      */
  121.     private int hashFunction(String key) {
  122.         return (getAsciiValue(key) % sizeOfMap);
  123.     }
  124.  
  125.  
  126.     /**
  127.      * Returns the sum of the key. Therefor it adds the asciivalue of each letter in the key.
  128.      *
  129.      * @param key
  130.      * @return sum
  131.      */
  132.     private int getAsciiValue(String key) {
  133.         int result = 0;
  134.         for (int i = 0; i < key.length(); i++) {
  135.             char character = key.charAt(i);
  136.             int asciiValue = (int) character;
  137.             result += asciiValue;
  138.         }
  139.         return result;
  140.     }
  141.  
  142.  
  143.     private void searchAndAdd(KeyValuePair root, String key, int value) {
  144.         if (root != null) {
  145.             KeyValuePair next = root;
  146.             boolean found = false;
  147.             while (!found && next != null) {
  148.                 if (next.getKey() == key) {
  149.                     found = true;
  150.                 } else {
  151.                     next = next.getNext();
  152.                 }
  153.             }
  154.             if (found) {
  155.                 next.setValue(value);
  156.             } else {
  157.                 hashMap[hashFunction(key)] = addToLinkedList(root, new KeyValuePair(key, value));
  158.             }
  159.         }
  160.     }
  161.  
  162.     /**
  163.      * Adds the linkedList to next.next and returns the new root.
  164.      *
  165.      * @param root
  166.      * @param next
  167.      * @return the new linkedList.
  168.      */
  169.     private KeyValuePair addToLinkedList(KeyValuePair root, KeyValuePair next) {
  170.         next.setNext(root);
  171.         return next;
  172.     }
  173.  
  174.  
  175.     /**
  176.      * Search key in the given LinkedList.
  177.      * @param key
  178.      * @param root
  179.      * @return -1 if key is not found or  the value of the KeyValuePair.
  180.      */
  181.     private int searchLinkedList(String key, KeyValuePair root) {
  182.         int value = -1;
  183.         if (root != null) {
  184.             KeyValuePair next = root;
  185.             boolean found = false;
  186.             while (!found && (next != null)) {
  187.                 if (next.getKey() == key) {
  188.                     value = next.getValue();
  189.                     found = true;
  190.                 } else {
  191.                     next = next.getNext();
  192.                 }
  193.             }
  194.         }
  195.         return value;
  196.     }
  197.  
  198.  
  199.     /**
  200.      * Initialise the hashMap.
  201.      *
  202.      * @param sizeOfMap
  203.      */
  204.     private void init(int sizeOfMap) {
  205.         this.sizeOfMap = sizeOfMap;
  206.         hashMap = new KeyValuePair[sizeOfMap];
  207.         fillWithNull(sizeOfMap);
  208.     }
  209.  
  210.  
  211.     /**
  212.      * Fills the array with null.
  213.      *
  214.      * @param sizeOfMap
  215.      */
  216.     private void fillWithNull(int sizeOfMap) {
  217.         for (int i = 0; i < sizeOfMap; i++) {
  218.             hashMap[i] = null;
  219.         }
  220.     }
  221. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement