HashMap 구현하기

• Static allocation + Single LinkedList

  #define MAX 1000000
  #define nullptr 0L

  typedef unsigned long long ull;

  struct Node {
      Node* prev;
      ull key;
      int data;
      bool isDeleted;
  }a[MAX];

  int midx;
  Node* hashTable[MAX];
  Node* malloc() {
      return &a[midx++];
  }

  ull toHash(const char* str) {
      int c = 0;
      ull value = 5381;

      while (c = *str++) {
          value = ((value << 5) + value) + c;
      }

      return value;
  }

  void init() {
      midx = 0;
      for (register int i = 0; i < MAX; ++i) {
          hashTable[i] = nullptr;
      }
  }

  int find(char key[])
  {
      ull hashValue = toHash(key);
      int hashedKey = hashValue % MAX;

      for (register Node* pp = hashTable[hashedKey]; pp != nullptr; pp = pp->prev) {
          if (!pp->isDeleted && pp->key == hashValue) {
              return pp->data;
          }
      }
  }

  void add(char key[], int data)
  {
      ull hashValue = toHash(key);
      int hashedKey = hashValue % MAX;

      Node* newNode = malloc();
      newNode->data = data;
      newNode->key = hashValue;
      newNode->isDeleted = false;

      newNode->prev = hashTable[hashedKey];
      hashTable[hashedKey] = newNode;
  }

  int remove(char key[])
  {
      ull hashValue = toHash(key);
      int hashedKey = hashValue % MAX;

      for (register Node* pp = hashTable[hashedKey]; pp != nullptr; pp = pp->prev) {
          if (!pp->isDeleted && pp->key == hashValue) {
              pp->isDeleted = true;
              return pp->data;
          }
      }
  }

• Dynamic allocation + Single LinkedList

  #define MAX 1000000
  #define nullptr 0L

  typedef unsigned long long ull;

  struct Node {
      Node* prev;
      ull key;
      int data;
      bool isDeleted;

      Node(ull key, int data): prev(nullptr), key(key), data(data), isDeleted(false) {};
  };

  Node* hashTable[MAX];

  ull toHash(const char* str) {
      int c = 0;
      ull value = 5381;

      while(c = *str++) {
          value = ((value << 5) + value) + c;
      }

      return value;
  }

  void init(){
      for(register int i = 0 ; i < MAX ; ++i) {
          hashTable[i] = nullptr;
      }
  }

  int find(char key[])
  {
      ull hashValue = toHash(key);
      int hashedKey = hashValue % MAX;

      for(register Node* pp = hashTable[hashedKey] ; pp != nullptr ; pp = pp->prev) {
          if(!pp->isDeleted && pp->key == hashValue) {
              return pp->data;
          }
      }
  }

  void add(char key[], int data)
  {
      ull hashValue = toHash(key);
      int hashedKey = hashValue % MAX;

      Node* newNode = new Node(hashValue, data);
      newNode->prev = hashTable[hashedKey];
      hashTable[hashedKey] = newNode;
  }

  int remove(char key[])
  {
      ull hashValue = toHash(key);
      int hashedKey = hashValue % MAX;

      for(register Node* pp = hashTable[hashedKey] ; pp != nullptr ; pp = pp->prev) {
          if(!pp->isDeleted && pp->key == hashValue) {
              pp->isDeleted = true;
              return pp->data;
          }
      }
  }

• Dynamic allocation + Double LinkedList

  #define DATA_MAX 1000001
  #define MAP_SIZE_MAX 100002
  #define nullptr 0L

  typedef unsigned long long ull;

  struct Node {
      Node* prev;
      Node* next;
      ull value;
      int data;

      Node(ull value, int data) : prev(nullptr), next(nullptr), value(value), data(data) {};
  };

  // 0: HEAD    1: TAIL
  Node* hashTable[MAP_SIZE_MAX][2];

  ull toHash(const char* str);
  int toHashedKey(ull value);

  void init() {
      for (int i = 0; i < MAP_SIZE_MAX; ++i) {
          hashTable[i][0] = new Node(-1, -1);
          hashTable[i][1] = new Node(-1, -1);
          hashTable[i][0]->next = hashTable[i][1];
          hashTable[i][1]->prev = hashTable[i][0];
          hashTable[i][0]->prev = nullptr;
          hashTable[i][1]->next = nullptr;
      }
  }

  void add(char key[], int data)
  {
      ull value = toHash(key);
      int hashedKey = toHashedKey(value);

      Node* newNode = new Node(value, data);
      newNode->prev = hashTable[hashedKey][1]->prev;
      hashTable[hashedKey][1]->prev = newNode;

      newNode->next = newNode->prev->next;
      newNode->prev->next = newNode;
  }

  int find(char key[])
  {
      ull value = toHash(key);
      int hashedKey = toHashedKey(value);

      for (Node* p = hashTable[hashedKey][0]; p != nullptr ; p = p->next) {
          if (p->value == value) {
              return p->data;
          }
      }
  }

  int remove(char key[])
  {
      ull value = toHash(key);
      int hashedKey = toHashedKey(value);

      for (Node* p = hashTable[hashedKey][0]; p != nullptr; p = p->next) {
          if (p->value == value) {
              int res = p->data;

              p->next->prev = p->prev;
              p->prev->next = p->next;

              delete p;
              return res;
          }
      }
  }

  ull toHash(const char* str) {
      int c = 0;
      ull value = 5381;

      while (c = *str++) {
          value = ((value << 5) + value) + c;
      }

      return value;
  }

  int toHashedKey(ull value) {
      return value % MAP_SIZE_MAX;
  }