Design HashMap

🏠 ⬅️ ➡️

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

  • MyHashMap() initializes the object with an empty map.
  • void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
  • int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
  • void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:

Input [ "MyHashMap ", "put ", "put ", "get ", "get ", "put ", "get ", "remove ", "get "] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]] Output [null, null, null, 1, -1, null, 1, null, -1]

Explanation MyHashMap myHashMap = new MyHashMap(); myHashMap.put(1, 1); // The map is now [[1,1]] myHashMap.put(2, 2); // The map is now [[1,1], [2,2]] myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]] myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]] myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value) myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]] myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]] myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]

Constraints:

  • 0 <= key, value <= 106
  • At most 104 calls will be made to put, get, and remove.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main

! This program solves the problem of implementing a HashMap without using any
! built-in hash table libraries.

implicit none

type :: MyHashMap
  private
  type(hash_map), allocatable :: map(:)
contains
  procedure :: put
  procedure :: get
  procedure :: remove
end type MyHashMap

interface
  subroutine put(this, key, value)
    import :: MyHashMap
    class(MyHashMap), intent(inout) :: this
    integer, intent(in) :: key
    integer, intent(in) :: value
  end subroutine put

  function get(this, key) result(value)
    import :: MyHashMap
    class(MyHashMap), intent(in) :: this
    integer, intent(in) :: key
    integer :: value
  end function get

  subroutine remove(this, key)
    import :: MyHashMap
    class(MyHashMap), intent(inout) :: this
    integer, intent(in) :: key
  end subroutine remove
end interface

type(MyHashMap), target :: my_hash_map
integer :: i, j, n, key, value
character(len=100) :: input_string
logical :: success

! Read the number of test cases
read(*,*) n

do i = 1, n
  ! Read the input string
  read(*,'(A)') input_string

  select case (input_string)
  case ("MyHashMap")
    allocate(my_hash_map%map(0))
  case ("put")
    read(*,*) key, value
    call my_hash_map%put(key, value)
  case ("get")
    read(*,*) key
    write(*,*) my_hash_map%get(key)
  case ("remove")
    read(*,*) key
    call my_hash_map%remove(key)
  end select
end do

contains

subroutine put(this, key, value)
  class(MyHashMap), intent(inout) :: this
  integer, intent(in) :: key
  integer, intent(in) :: value
  integer :: index

  ! Find the index where the key should be inserted
  index = find_index(this%map, key)

  ! Insert the key-value pair at the appropriate position
  if (index == 0) then
    allocate(this%map(size(this%map)+1))
    this%map(size(this%map))%key = key
    this%map(size(this%map))%value = value
  else
    this%map(index)%value = value
  end if
end subroutine put

function get(this, key) result(value)
  class(MyHashMap), intent(in) :: this
  integer, intent(in) :: key
  integer :: value
  integer :: index

  ! Find the index where the key is located
  index = find_index(this%map, key)

  ! Return the value associated with the key
  if (index /= 0) then
    value = this%map(index)%value
  else
    value = -1
  end if
end function get

subroutine remove(this, key)
  class(MyHashMap), intent(inout) :: this
  integer, intent(in) :: key
  integer :: index

  ! Find the index where the key is located
  index = find_index(this%map, key)

  ! Remove the key-value pair from the map
  if (index /= 0) then
    deallocate(this%map(index)%key)
    deallocate(this%map(index)%value)
    this%map(index) = this%map(size(this%map))
    deallocate(this%map(size(this%map)))
  end if
end subroutine remove

recursive function find_index(map, key) result(index)
  type(hash_map), intent(in) :: map(:)
  integer, intent(in) :: key
  integer :: index

  ! Base case: the key is not found
  if (.not. allocated(map)) then
    index = 0
    return
  end if

  ! Recursive case: compare the key with the current element
  if (
❌ Compiled
❌ Executed
❌ Correct 
! This is a full Fortran script with a valid main entry point that solves the problem described above.

module MyHashMap
    implicit none

    type :: MyHashMap
        private
        integer, allocatable :: keys(:)
        integer, allocatable :: values(:)
        integer :: size = 0
    contains
        procedure, public :: put
        procedure, public :: get
        procedure, public :: remove
    end type MyHashMap

    interface MyHashMap
        module procedure constructor
    end interface MyHashMap

contains

    function constructor() result(this)
        type(MyHashMap) :: this

        allocate(this%keys(0))
        allocate(this%values(0))
    end function constructor

    subroutine put(this, key, value)
        class(MyHashMap), intent(inout) :: this
        integer, intent(in) :: key
        integer, intent(in) :: value

        integer :: i

        ! Check if the key already exists
        do i = 1, this%size
            if (this%keys(i) == key) then
                this%values(i) = value
                return
            end if
        end do

        ! If the key does not exist, add it to the map
        this%size = this%size + 1
        allocate(this%keys(this%size))
        allocate(this%values(this%size))
        this%keys(this%size) = key
        this%values(this%size) = value
    end subroutine put

    function get(this, key) result(value)
        class(MyHashMap), intent(in) :: this
        integer, intent(in) :: key
        integer :: value

        integer :: i

        ! Check if the key exists
        do i = 1, this%size
            if (this%keys(i) == key) then
                value = this%values(i)
                return
            end if
        end do

        ! If the key does not exist, return -1
        value = -1
    end function get

    subroutine remove(this, key)
        class(MyHashMap), intent(inout) :: this
        integer, intent(in) :: key

        integer :: i

        ! Check if the key exists
        do i = 1, this%size
            if (this%keys(i) == key) then
                this%size = this%size - 1
                this%keys(i) = this%keys(this%size + 1)
                this%values(i) = this%values(this%size + 1)
                return
            end if
        end do
    end subroutine remove
end module MyHashMap

program main
    use MyHashMap
    implicit none

    type(MyHashMap) :: myHashMap
    integer :: key, value

    ! Test case 1:
    call myHashMap%put(1, 1)
    call myHashMap%put(2, 2)
    value = myHashMap%get(1)
    print *, value
    value = myHashMap%get(3)
    print *, value
    call myHashMap%put(2, 1)
    value = myHashMap%get(2)
    print *, value
    call myHashMap%remove(2)
    value = myHashMap%get(2)
    print *, value

    ! Test case 2:
    call myHashMap%put(1, 1)
    call myHashMap%put(2, 2)
    call myHashMap%put(3, 3)
    call myHashMap%remove(3)
    call myHashMap%remove(2)
    call myHashMap%remove(1)

    ! Test case 3:
    call myHashMap%put(1, 1)
    call myHashMap%put(2, 2)
    call myHashMap%put(3, 3)
    call myHashMap%put(4, 4)
    call myHashMap%put(5, 5)
    call myHashMap%put(6, 6)
    call myHashMap%put(7, 7)
    call myHashMap%put(8, 8)
    call myHashMap%put(9, 9)
    call myHashMap%put(10, 10)
    call myHashMap%remove(10)
🌐 Data from online sources 
class MyHashMap:
    def __init__(self):
        self.size = 10007
        self.data = [[] for _ in range(self.size)]

    def put(self, key: int, value: int) -> None:
        bucket = self.data[key % self.size]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])

    def get(self, key: int) -> int:
        bucket = self.data[key % self.size]
        for pair in bucket:
            if pair[0] == key:
                return pair[1]
        return -1

    def remove(self, key: int) -> None:
        bucket = self.data[key % self.size]
        for i, pair in enumerate(bucket):
            if pair[0] == key:
                bucket.pop(i)
                return

The basic strategy for a simple hash map, given that the number of keys will be at most 10^4, is to use a hashing function to map an integer key to an index in an array or list of "buckets". We will use the modulo operation to do this, with a prime number for the size (e.g., 10007) to minimize the likelihood of collisions.

Each "bucket" is a list that can store the (key, value) pairs with the same hash. When a collision happens (i.e., two keys share the same hash), we simply append the new value to the list of that same "bucket". We use separate chaining in the linked list, which means that if two values collide, they will coexist in the same bucket.

To perform the put operation, we first hash the key modulo the size to find the corresponding bucket. We iterate through this bucket to check if the key already exists; if so, we update its value, and otherwise, we insert a new (key, value) pair at the end of the list.

The get operation works similarly to put: we find the corresponding bucket by hashing the key modulo the size, then iterate through the list to find the requested key. If we find the key, we return the associated value; otherwise, we return -1 to indicate that the key is not in the hash map.

For the remove operation, we again find the corresponding bucket, then iterate through the list to find the pair with the matching key, and remove it from the list if found.

The complexity of this solution is O(N/K) for each operation (where N is the number of all possible keys and K is the size of the array), but if the number of keys is much smaller than the size of the array, the operations are sufficiently quick.

🌐 Data from online sources 
class MyHashMap {
public:
    vector<list<pair<int, int>>> data;
    static const int size = 10007;

    MyHashMap() {
        data = vector<list<pair<int, int>>>(size);
    }

    void put(int key, int value) {
        auto& bucket = data[key % size];
        for (auto& pair : bucket) {
            if (pair.first == key) {
                pair.second = value;
                return;
            }
        }
        bucket.emplace_back(key, value);
    }

    int get(int key) {
        const auto& bucket = data[key % size];
        for (const auto& pair : bucket) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        return -1;
    }

    void remove(int key) {
        auto& bucket = data[key % size];
        bucket.remove_if([key](const auto& pair) { return pair.first == key; });
    }
};

The basic strategy for a simple hash map, given that the number of keys will be at most 10^4, is to use a hashing function to map an integer key to an index in an array or list of "buckets". We will use the modulo operation to do this, with a prime number for the size (e.g., 10007) to minimize the likelihood of collisions.

Each "bucket" is a list that can store the (key, value) pairs with the same hash. When a collision happens (i.e., two keys share the same hash), we simply append the new value to the list of that same "bucket". We use separate chaining in the linked list, which means that if two values collide, they will coexist in the same bucket.

To perform the put operation, we first hash the key modulo the size to find the corresponding bucket. We iterate through this bucket to check if the key already exists; if so, we update its value, and otherwise, we insert a new (key, value) pair at the end of the list.

The get operation works similarly to put: we find the corresponding bucket by hashing the key modulo the size, then iterate through the list to find the requested key. If we find the key, we return the associated value; otherwise, we return -1 to indicate that the key is not in the hash map.

For the remove operation, we again find the corresponding bucket, then iterate through the list to find the pair with the matching key, and remove it from the list if found.

The complexity of this solution is O(N/K) for each operation (where N is the number of all possible keys and K is the size of the array), but if the number of keys is much smaller than the size of the array, the operations are sufficiently quick.