HashMap 구현

Time complexity 시간 복잡도

 

 

 

class Pair:
    def __init__(self, key, val):
        self.key = key
        self.val = val

class HashMap:
    def __init__(self):
        self.size = 0
        self.capacity = 2
        self.map = [None, None]
    
    def hash(self, key):
        index = 0
        for c in key:
            index += ord(c)
        return index % self.capacity

    def get(self, key):
        index = self.hash(key)
        
        while self.map[index] != None:
            if self.map[index].key == key:
                return self.map[index].val
            index += 1
            index = index % self.capacity
        return None

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

        while True:
            if self.map[index] == None:
                self.map[index] = Pair(key, val)
                self.size += 1
                if self.size >= self.capacity // 2:
                    self.rehash()
                return
            elif self.map[index].key == key:
                self.map[index].val = val
                return
            
            index += 1
            index = index % self.capacity
    
    def remove(self, key):
        if not self.get(key):
            return
        
        index = self.hash(key)
        while True:
            if self.map[index].key == key:
                # Removing an element using open-addressing actually causes a bug,
                # because we may create a hole in the list, and our get() may 
                # stop searching early when it reaches this hole.
                self.map[index] = None
                self.size -= 1
                return
            index += 1
            index = index % self.capacity

    def rehash(self):
        self.capacity = 2 * self.capacity
        newMap = []
        for i in range(self.capacity):
            newMap.append(None)

        oldMap = self.map
        self.map = newMap
        self.size = 0
        for pair in oldMap:
            if pair:
                self.put(pair.key, pair.val)
    
    def print(self):
        for pair in self.map:
            if pair:
                print(pair.key, pair.val)

 

#include <vector>
#include <string>
#include <utility>
#include <iostream>

using std::vector;
using std::string;
using std::pair;
using std::cout;
using std::endl;

class HashMap {
public:
    int size_ = 0;
    int capacity_ = 2;
    vector<pair<string, string>*> map_;

    HashMap() {
        map_ = *(new vector<pair<string, string>*> {0, 0});
    }

    int hash(string& key) {
        int index = 0;
        for (char &c: key) {
            index += int(c);
        }
        return index % capacity_;
    }

    string* get(string& key) {
        int index = hash(key);
        while (map_[index]) {
            if (map_[index]->first == key) {
                return &map_[index]->second;
            }
            index++;
            index = index % capacity_;
        }
        return nullptr;
    }

    void put(string& key, string& val) {
        int index = hash(key);
        while (true) {
            if (map_[index] == 0) {
                map_[index] = new pair<string, string>(key, val);
                size_++;
                if (size_ >= capacity_ / 2) {
                    rehash();
                }
                return;
            } else if (map_[index]->first == key) {
                map_[index]->second = val;
                return;
            }
            index++;
            index = index % capacity_;
        }
    }

    void remove(string& key) {
        if (!get(key)) {
            return;
        }
        int index = hash(key);
        while (true) {
            if (map_[index]->first == key) {
                // Removing an element using open-addressing actually causes a bug,
                // because we may create a hole in the list, and our get() may 
                // stop searching early when it reaches this hole.
                map_[index] = 0;
                size_--;
                return;
            }
            index++;
            index = index % capacity_;
        }
    }

    void rehash() {
        capacity_ = 2 * capacity_;
        vector<pair<string, string>*> newMap = *(new vector<pair<string, string>*>());

        for (int i = 0; i < capacity_; i++) {
            newMap.push_back(0);
        }
        vector<pair<string, string>*> oldMap = map_;
        map_ = newMap;
        size_ = 0;
        for (auto& pair: oldMap) {
            if (pair != 0) {
                put(pair->first, pair->second);
            }
        }
    }

    void print() {
        cout << "Printing size=" << size_ << endl; 
        for (auto& pair: map_) {
            if (pair) {
                cout << pair->first << ' ' << pair->second << '-';
            }
            cout << endl;
        }
    }
};