KurKing

Hash Map Team#1

Apr 20th, 2021 (edited)
477
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package com.kpi.fict.it01.haspmap;
  2.  
  3. import java.util.ArrayList;
  4.  
  5. public class HashMap<Value> {
  6.  
  7.     private ArrayList<Node<Value>> buckets;
  8.     private int bucketsAmount;
  9.     private int size;
  10.  
  11.     public HashMap() {
  12.         buckets = new ArrayList<>(16);
  13.         bucketsAmount = 16;
  14.         size = 0;
  15.  
  16.         for (int i = 0; i < bucketsAmount; i++)
  17.             buckets.add(null);
  18.     }
  19.  
  20.     public int getSize() {
  21.         return size;
  22.     }
  23.  
  24.     public Value get(String key) {
  25.         Node<Value> node = buckets.get(getBucketIndex(key));
  26.         while (node != null) {
  27.             if (node.key.equals(key))
  28.                 return node.value;
  29.             node = node.nextNode;
  30.         }
  31.         return null;
  32.     }
  33.  
  34.     public void remove(String key) {
  35.         int bucketIndex = getBucketIndex(key);
  36.  
  37.         Node<Value> nodeToRemove = buckets.get(bucketIndex);
  38.         if (nodeToRemove == null) return;
  39.  
  40.         Node<Value> previousNode = null;
  41.         while (nodeToRemove != null) {
  42.             if (nodeToRemove.key.equals(key))
  43.                 break;
  44.             previousNode = nodeToRemove;
  45.             nodeToRemove = nodeToRemove.nextNode;
  46.         }
  47.         size -= 1;
  48.  
  49.         if (previousNode != null) {
  50.             if (nodeToRemove == null) {
  51.                 return;
  52.             }
  53.             previousNode.nextNode = nodeToRemove.nextNode;
  54.         } else {
  55.             buckets.set(bucketIndex, nodeToRemove.nextNode);
  56.         }
  57.     }
  58.  
  59.     public ArrayList<Value> toArray() {
  60.         ArrayList<Value> result = new ArrayList<>();
  61.  
  62.         for (Node<Value> node: buckets) {
  63.             while (node != null) {
  64.                 result.add(node.value);
  65.                 node = node.nextNode;
  66.             }
  67.         }
  68.  
  69.         return result;
  70.     }
  71.  
  72.     public void add(String key, Value value) {
  73.         int bucketIndex = getBucketIndex(key);
  74.         Node<Value> nodeAfterInserted = buckets.get(bucketIndex);
  75.  
  76.         while (nodeAfterInserted != null) {
  77.             if (nodeAfterInserted.key.equals(key)) {
  78.                 nodeAfterInserted.value = value;
  79.                 return;
  80.             }
  81.             nodeAfterInserted = nodeAfterInserted.nextNode;
  82.         }
  83.  
  84.         size++;
  85.         nodeAfterInserted = buckets.get(bucketIndex);
  86.         Node<Value> newNode = new Node(key, value);
  87.         newNode.nextNode = nodeAfterInserted;
  88.         buckets.set(bucketIndex, newNode);
  89.  
  90.         if (!isLoadFactorAcceptable()) {
  91.             ensureCapacity();
  92.         }
  93.     }
  94.  
  95.     private void ensureCapacity() {
  96.         ArrayList<Node<Value>> temp = buckets;
  97.         size = 0;
  98.         bucketsAmount *= 2;
  99.         buckets = new ArrayList<>(bucketsAmount);
  100.  
  101.         for (int i = 0; i < bucketsAmount; i++)
  102.             buckets.add(null);
  103.  
  104.         for (Node<Value> node : temp) {
  105.             while (node != null) {
  106.                 add(node.key, node.value);
  107.                 node = node.nextNode;
  108.             }
  109.         }
  110.     }
  111.  
  112.     private boolean isLoadFactorAcceptable() {
  113.         return (1.0*size/bucketsAmount) <= 0.7;
  114.     }
  115.  
  116.     private int getBucketIndex(String key) {
  117.         return Math.abs(getHashCode(key) % bucketsAmount);
  118.     }
  119.  
  120.     private static int getHashCode(String key) {
  121.         double smallNumber = 79;
  122.         double bigNumber = 27644437;
  123.         double multiplier = 1;
  124.         int hashCode = 0;
  125.  
  126.         for (char i : key.toCharArray()) {
  127.             hashCode += ((int) i) * multiplier % bigNumber;
  128.             multiplier = multiplier * smallNumber % bigNumber;
  129.         }
  130.  
  131.         return hashCode;
  132.     }
  133.  
  134.     private class Node<Value> {
  135.         String key;
  136.         Value value;
  137.  
  138.         Node<Value> nextNode;
  139.  
  140.         public Node(String key, Value value) {
  141.             this.key = key;
  142.             this.value = value;
  143.         }
  144.     }
  145. }
  146.  
RAW Paste Data