نگاهی عمیق به map در برنامه نویسی

a := 24
b := 24
c := 52

(a = b) != c  ∴ (a.hashcode = b.hashcode) != c.hashcode
        

class Entry{
  K key
  V value

  function getKey(): K{
    return key
  }

  function getValue(): V{
    return value
  }

  function setValue(newValue: V): V{
    oldValue := value
    value := newValue
    return oldValue
  }

}
        

function hash(K key): int{
  
  int h = key.hashcode
  h = h ^ (h >>> 16)

  return h & (buckets.length - 1)
}
        

class MyHashMap{

  loadFactor := 0.75
  capacity := 16
  size := 0

  buckets := new LinkedList[capacity]

  function resize(){
    oldBuckets := buckets

    mSize := 0
    mCapacity := mCapacity * 2

    buckets := new LinkedList[mSize]

    for 0 <= i < oldBuckets.length
      
      bucket := oldBuckets[i]

      if bucket != null
        for 0 <= j < bucket.size
          put(bucket.key, bucket.value)

  }
        

function get(key: K): V{
  
  index := hash(key)

  bucket := buckets[index]

  if bucket != null
    for 0 <= i < bucket.size
      
      entry := bucket.get(i)
      
      if entry.key = key
        return entry.value

  return null
}
        

function contains(key: K): boolean{
  
  return get(key) != null
}
        

function put(key: K, value: V): V{

  index := hash(key)

  if index < 0 
    return null

  if contains(key)
    for 0<= i < buckets[index].size
      entry := buckets[index].get(i)
      if entry.key = key
        return entry.setValue(value)
  else
  
    if size >= loadFactor * capacity
      resize()

    if buckets[index] = null
      buckets[index] := new LinkedList()


    buckets[index].add(new Entry(key, value))

    size++

}
        

function remove(key: K): V{

  if contains(key)
    
    index := hash(key)

    bucket := buckets[index]

    for 0<= i < bucket.size
      if bucket.get(i).key = key
        return bucket.remove(i)
        
    size--

  return null
}
        

import java.util.LinkedList;

public class MyHashMap<K, V> {

    private static final int DEFAULT_CAPACITY = 16;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private int capacity;
    private float loadFactor;

    private int size = 0;

    private LinkedList<Entry<K, V>>[] buckets;

    public MyHashMap(int capacity, float loadFactor) {
        if (loadFactor <= 0 || loadFactor > 1)
            throw new IllegalArgumentException("load factor should be greater than 0 and less than or equal 1");
        if (capacity <= 0) throw new IllegalArgumentException("Capacity can not be zero or less");
        this.loadFactor = loadFactor;
        this.capacity = capacity;

        buckets = (LinkedList<Entry<K, V>>[]) new LinkedList[capacity];
    }

    public MyHashMap(int capacity) {
        this(capacity, DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap() {
        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public int hash(K key) {
        if (key == null) return -1;

        int h = key.hashCode();
        h = h ^ (h >>> 16);

        return h & (capacity - 1);
    }

    public V get(K key) {

        int index = hash(key);
        LinkedList<Entry<K, V>> bucket = buckets[index];

        if (bucket != null) {
            for (Entry<K, V> entry : bucket)
                if (entry.getKey().equals(key))
                    return entry.getValue();
        }

        return null;
    }

    public boolean containsKey(K key) {
        return get(key) != null;
    }

    public V put(K key, V value) {

        int index = hash(key);

        if (index < 0) return null;

        if (size >= capacity * loadFactor) resize();

        LinkedList<Entry<K, V>> bucket = buckets[index];

        if (containsKey(key)) {

            for (Entry<K, V> entry : bucket) {
                if (entry.getKey().equals(key)) {
                    return entry.setValue(value);
                }
            }

        } else {

            if (bucket == null)  buckets[index] = new LinkedList<>();

            buckets[index].add(new Entry<>(key, value));

            size++;
        }

        return value;
    }

    public V remove(K key) {

        if (containsKey(key)){

            int index = hash(key);
            LinkedList<Entry<K, V>> bucket = buckets[index];

            for (int i=0; i<bucket.size(); i++){
                if (bucket.get(i).getKey().equals(key))
                    return bucket.remove(i).getValue();
            }

            size--;
        }

        return null;
    }

    public int getSize() {
        return size;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        LinkedList<Entry<K, V>>[] oldBuckets = buckets;
        size = 0;
        capacity *= 2;
        buckets = (LinkedList<Entry<K, V>>[]) new LinkedList[capacity];

        for (LinkedList<Entry<K, V>> bucket : oldBuckets) {
            if (bucket != null) {
                for (Entry<K, V> entry : bucket) {
                    put(entry.getKey(), entry.getValue());
                }
            }
        }
    }

    @Override
    public String toString() {


        StringBuilder sb = new StringBuilder();

        sb.append("[ ");

                for(LinkedList<Entry<K, V>> bucket : buckets){
                    if (bucket != null)
                        for (Entry<K, V> entry : bucket)
                            sb.append(entry).append(" ");
                }

                    sb.append(" ]");

        return sb.toString();
    }


    public static class Entry<K, V> {
        private final K key;
        private V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        @Override
        public String toString() {
            return "{" + getKey() + " : " + getValue() + "}";
        }
    }
}
        

class MyHashMap<K, V> (var capacity: Int = DEFAULT_CAPACITY,val loadFactor: Float = DEFAULT_LOAD_FACTOR) {

    var size: Int = 0
        private set

    private var buckets: Array<LinkedList<Entry<K?, V?>>?>

    init {
        require(!(loadFactor <= 0 || loadFactor > 1)) { "load factor should be greater than 0 and less than or equal 1" }
        require(capacity > 0) { "Capacity can not be zero or less" }

        buckets = arrayOfNulls(capacity)
    }

    fun hash(key: K?): Int {
        if (key == null) return -1

        var h = key.hashCode()
        h = h xor (h ushr  16)

        return h and (capacity - 1)
    }

    fun get(key: K?): V? {
        val index = hash(key)
        val bucket: LinkedList<Entry<K?, V?>>? = buckets[index]

        if (bucket != null) {
            for (entry in bucket) if (entry.key == key) return entry.value
        }

        return null
    }

    fun containsKey(key: K?): Boolean {
        return get(key) != null
    }

    fun put(key: K?, value: V?): V? {
        val index = hash(key)

        if (index < 0) return null

        if (size >= capacity * loadFactor) resize()

        val bucket: LinkedList<Entry<K?, V?>>? = buckets[index]

        if (containsKey(key)) {
            for (entry in bucket!!) {
                if (entry.key == key) {
                    return entry.setValue(value)
                }
            }
        } else {

            if (bucket == null) buckets[index] = LinkedList<Entry<K?, V?>>()

            buckets[index]!!.add(Entry(key, value))

            size++
        }

        return value
    }

    fun remove(key: K?): V? {
        if (containsKey(key)) {
            val index = hash(key)
            val bucket: LinkedList<Entry<K?, V?>>? = buckets[index]

            for (i in bucket!!.indices) {
                if (bucket[i].key == key) return bucket.removeAt(i).value
            }

            size--
        }

        return null
    }

    private fun resize() {
        val oldBuckets = buckets
        size = 0
        capacity *= 2
        buckets = arrayOfNulls(capacity)

        for (bucket in oldBuckets) {
            if (bucket != null) {
                for (entry in bucket) {
                    put(entry.key, entry.value)
                }
            }
        }
    }

    override fun toString(): String {
        val sb = StringBuilder()

        sb.append("[ ")

        for (bucket in buckets) {
            if (bucket != null) for (entry in bucket) sb.append(entry).append(" ")
        }

        sb.append(" ]")

        return sb.toString()
    }

    data class Entry<K, V>(val key: K?, var value: V?) {
        fun setValue(value: V): V? {
            val oldValue = this.value
            this.value = value
            return oldValue
        }

        override fun toString(): String {
            return "{" + this.key + " : " + this.value + "}"
        }
    }

    companion object {
        private const val DEFAULT_CAPACITY = 16
        private const val DEFAULT_LOAD_FACTOR = 0.75f
    }
}