آموزش کامل پیاده‌سازی Map در ساختمان داده

entries := new LinkedList[capacity]
          

entries := new Entry[capacity]
          

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) {
        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)) {
                    size--;
                    return bucket.remove(i).getValue();
                }
            }

        }

        return 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)){
                    size--;
                    return bucket.remove(i).getValue();
                }
            }

        }

        return null;
    }

    public Entry<K, V>[] toArray() {

        Entry<K, V>[] entries = (Entry<K, V>[]) new Entry[size];

        int index = 0;
        for (LinkedList<Entry<K, V>> list : buckets) {
            if (list != null) {
                for (Entry<K, V> entry : list) {
                    if (entry != null) {
                        entries[index++] = entry;
                    }
                }
            }
        }

        return entries;
    
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    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 {
        val index = hash(key)
        val bucket: LinkedList<Entry<K?, V?>>? = buckets[index]

        if (bucket != null)
            for (entry in bucket) if (entry.key == key) return true

        return false
    }

    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
    }

    fun toArray(): Array<Entry<K?, V?>?> {

        val entries: Array<Entry<K?, V?>?> = arrayOfNulls(size)

        var index = 0
        for (list in buckets) {
            if (list != null) {
                for (entry in list) {
                    entries[index++] = entry
                }
            }
        }

        return entries
    }

    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
    }
}

        

class MyHashMap {
    static DEFAULT_CAPACITY = 16;
    static DEFAULT_LOAD_FACTOR = 0.75;

    // Nested Entry Class
    static Entry = class {
        constructor(key, value) {
            this.key = key;
            this.value = value;
        }

        getKey() {
            return this.key;
        }

        getValue() {
            return this.value;
        }

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

        toString() {
            return "{" + this.getKey() + " : " + this.getValue() + "}";
        }
    };

    constructor(capacity = MyHashMap.DEFAULT_CAPACITY, loadFactor = MyHashMap.DEFAULT_LOAD_FACTOR) {
        if (loadFactor <= 0 || loadFactor > 1)
            throw new Error("load factor should be greater than 0 and less than or equal 1");
        if (capacity <= 0) throw new Error("Capacity can not be zero or less");
        
        this.loadFactor = loadFactor;
        this.capacity = capacity;
        this.size = 0;

        this.buckets = new Array(capacity).fill(null);
    }

    hash(key) {
        if (key === null || key === undefined) return -1;

        // Custom simple hash code generator to mimic Java's .hashCode()
        let h = 0;
        const s = String(key);
        for (let i = 0; i < s.length; i++) {
            h = (31 * h + s.charCodeAt(i)) | 0;
        }
        
        h = h ^ (h >>> 16);
        return h & (this.capacity - 1);
    }

    get(key) {
        const index = this.hash(key);
        const bucket = this.buckets[index];

        if (bucket !== null) {
            // Using getSize() from our custom MyLinkedList implementation
            for (let i = 0; i < bucket.getSize(); i++) {
                const entry = bucket.get(i);
                if (entry.getKey() === key)
                    return entry.getValue();
            }
        }

        return null;
    }

    containsKey(key) {
            const index = this.hash(key);
            const bucket = this.buckets[index];

            for (let i = 0; i < bucket.getSize(); i++) {
                if (bucket.get(i).getKey() === key) {
                    return true;
                }
            }
        }
        return false;
    }

    put(key, value) {
        const index = this.hash(key);

        if (index < 0) return null;

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

        const bucket = this.buckets[index];

        if (this.containsKey(key)) {
            for (let i = 0; i < bucket.getSize(); i++) {
                const entry = bucket.get(i);
                if (entry.getKey() === key) {
                    return entry.setValue(value);
                }
            }
        } else {
            if (this.buckets[index] === null) this.buckets[index] = new MyLinkedList();

            this.buckets[index].addLast(new MyHashMap.Entry(key, value));
            this.size++;
        }

        return value;
    }

    remove(key) {
        if (this.containsKey(key)) {
            const index = this.hash(key);
            const bucket = this.buckets[index];

            for (let i = 0; i < bucket.getSize(); i++) {
                if (bucket.get(i).getKey() === key) {
                    this.size--;
                    return bucket.remove(i).getValue();
                }
            }
        }

        return null;
    }

    toArray() {
        const entries = new Array(this.size);
        let index = 0;
        
        for (let i = 0; i < this.buckets.length; i++) {
            const list = this.buckets[i];
            if (list !== null) {
                for (let j = 0; j < list.getSize(); j++) {
                    const entry = list.get(j);
                    if (entry !== null) {
                        entries[index++] = entry;
                    }
                }
            }
        }

        return entries;
    }

    getSize() {
        return this.size;
    }

    isEmpty() {
        return this.size === 0;
    }

    resize() {
        const oldBuckets = this.buckets;
        this.size = 0;
        this.capacity *= 2;
        this.buckets = new Array(this.capacity).fill(null);

        for (let i = 0; i < oldBuckets.length; i++) {
            const bucket = oldBuckets[i];
            if (bucket !== null) {
                for (let j = 0; j < bucket.getSize(); j++) {
                    const entry = bucket.get(j);
                    this.put(entry.getKey(), entry.getValue());
                }
            }
        }
    }

    toString() {
        let sb = "[ ";
        for (let i = 0; i < this.buckets.length; i++) {
            const bucket = this.buckets[i];
            if (bucket !== null) {
                for (let j = 0; j < bucket.getSize(); j++) {
                    const entry = bucket.get(j);
                    sb += entry.toString() + " ";
                }
            }
        }
        sb += " ]";
        return sb;
    }
}
        

import MyLinkedList

class MyHashMap:
    DEFAULT_CAPACITY = 16
    DEFAULT_LOAD_FACTOR = 0.75

    # Nested Entry Class
    class Entry:
        def __init__(self, key, value):
            self.key = key
            self.value = value

        def get_key(self):
            return self.key

        def get_value(self):
            return self.value

        def set_value(self, value):
            oldValue = self.value
            self.value = value
            return oldValue

        def __str__(self):
            return "{" + str(self.get_key()) + " : " + str(self.get_value()) + "}"

    def __init__(self, capacity=DEFAULT_CAPACITY, load_factor=DEFAULT_LOAD_FACTOR):
        if load_factor <= 0 or load_factor > 1:
            raise ValueError("load factor should be greater than 0 and less than or equal 1")
        if capacity <= 0: 
            raise ValueError("Capacity can not be zero or less")
        
        self.load_factor = load_factor
        self.capacity = capacity
        self._size = 0

        self.buckets = [None] * capacity

    def hash(self, key):
        if key is None: return -1

        h = hash(key)
        h = h ^ (h >> 16)

        return h & (self.capacity - 1)

    def get(self, key):
        index = self.hash(key)
        bucket = self.buckets[index]

        if bucket is not None:
            for i in range(bucket._size):
                entry = bucket.get(i)
                if entry.get_key() == key:
                    return entry.get_value()

        return None

    def contains_key(self, key):
      
        index = self.hash(key)
        bucket = self.buckets[index]

        for i in range(bucket._size):
            if bucket.get(i).get_key() == key:
                return True
        return False

    def put(self, key, value):
        index = self.hash(key)

        if index < 0: return None

        if self._size >= self.capacity * self.load_factor: 
            self.resize()

        bucket = self.buckets[index]

        if self.contains_key(key):
            for i in range(bucket._size):
                entry = bucket.get(i)
                if entry.getKey() == key:
                    return entry.set_value(value)
        else:
            if self.buckets[index] is None: 
                self.buckets[index] = MyLinkedList()

            self.buckets[index].add_last(self.Entry(key, value))
            self._size += 1

        return value

    def remove(self, key):
        if self.contains_key(key):
            index = self.hash(key)
            bucket = self.buckets[index]

            for i in range(bucket._size):
                if bucket.get(i).get_key() == key:
                    self._size -= 1
                    return bucket.remove(i).get_value()

        return None

    def to_array(self):
        entries = [None] * self._size
        index = 0
        
        for list_obj in self.buckets:
            if list_obj is not None:
                for j in range(list_obj._size):
                    entry = list_obj.get(j)
                    if entry is not None:
                        entries[index] = entry
                        index += 1

        return entries

    def is_empty(self):
        return self._size == 0

    def resize(self):
        old_buckets = self.buckets
        self._size = 0
        self.capacity *= 2
        self.buckets = [None] * self.capacity

        for bucket in old_buckets:
            if bucket is not None:
                for j in range(bucket._size):
                    entry = bucket.get(j)
                    self.put(entry.get_key(), entry.get_value())

    def __str__(self):
        sb = "[ "
        for bucket in self.buckets:
            if bucket is not None:
                for j in range(bucket._size):
                    entry = bucket.get(j)
                    sb += str(entry) + " "
        sb += " ]"
        return sb