Неправильный ответ в задаче на пары (HashMap Java)

В задаче даны пары, затем на приходящий элемент требуется вывести его "соседа" по паре. Возникает ошибка в том, что происходит неправильный вывод. Предполагаю, что виной тому коллизии, так как при них возникает замена. Подскажите, как можно разрешить проблему (не сильно увеличивая вместимость мапы).

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Objects;

interface IMap<K, V> {

  V get(Object k);

  void put(K k, V v);

  V remove(Object k);

  boolean containsKey(Object k);

  boolean containsValue(Object v);

  int size();
}

public class Main {

  public static void main(String[] args) throws IOException {
    MyHashMap<String, String> map1 = new MyHashMap<>();
    MyHashMap<String, String> map2 = new MyHashMap<>();
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String S1 = reader.readLine();
    int n = Integer.parseInt(S1);
    for (int i = 0; i < n; i++) {
      String Str = reader.readLine();
      String[] a = Str.split(" ");
      map1.put(a[0], a[1]);
      map2.put(a[1], a[0]);
    }
    String S2 = reader.readLine();
    int m = Integer.parseInt(S2);
    for (int i = 0; i < m; i++) {
      String str = reader.readLine();
      if (map1.containsKey(str)) {
        System.out.println(map1.get(str));
      } else {
        System.out.println(map2.get(str));
      }
    }
  }
}

class MyHashMap<K, V> implements IMap<K, V> {

  private static final int DEFAULT_CAPACITY = 16;
  private static final int MAX_CAPACITY = 1 << 30;
  private static final float DEFAULT_LOAD_FACTOR = 0.75f;
  private final float loadFactor;
  private int size;
  private int threshHold;
  private Entry<K, V>[] table;

  @SuppressWarnings("unchecked")
  public MyHashMap(int capacity, float loadFactor) {
    if (capacity < 0) {
      throw new IllegalArgumentException("Illegal capacity: " + capacity);
    }
    if (loadFactor < 0 || Float.isNaN(loadFactor)) {
      throw new IllegalArgumentException("Illegal loadFactor: " + loadFactor);
    }
    if (capacity > MAX_CAPACITY) {
      capacity = MAX_CAPACITY;
    }
    int cap = 1;
    while (cap < capacity) {
      cap <<= 1;
    }
    this.threshHold = (int) (cap * loadFactor);
    this.loadFactor = loadFactor;
    this.table = (Entry<K, V>[]) new Entry[cap];
  }

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

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

  static int hash(int h, int length) {
    h ^= (h >>> 20) ^ (h >>> 12);
    h ^= (h >>> 7) ^ (h >>> 4);
    return h & (length - 1);
  }

  @Override
  public V get(Object key) {
    if (key == null) {
      if (table[0] == null) {
        return null;
      }
      Entry<K, V> tE = table[0];
      while (tE.key != null) {
        if (tE.next == null) {
          return null;
        }
        tE = tE.next;
      }
      return tE.value;
    } else {
      int hashKey = hash(key.hashCode(), table.length);
      if (table[hashKey] == null) {
        return null;
      } else {
        Entry<K, V> tE = table[hashKey];
        while (tE.key == null || !(tE.key.equals(key))) {
          if (tE.next == null) {
            return null;
          } else {
            tE = tE.next;
          }
        }
        return tE.value;
      }
    }
  }

  @Override
  public void put(K key, V value) {
    if (size > threshHold) {
      resize(2 * table.length);
    }
    if (key == null) {
      if (table[0] == null) {
        Entry<K, V> newE = new Entry<>(null, value, null);
        table[0] = newE;
        size++;
      } else {
        Entry<K, V> e = table[0];
        while (e.key != null) {
          if (e.key == null) {
            Entry<K, V> newE = new Entry<>(null, value, table[0]);
            table[0] = newE;
            size++;
            return;
          } else {
            e = e.next;
          }
        }
        e.value = value;
      }
    } else {
      int hashKey = hash(key.hashCode(), table.length);
      if (table[hashKey] == null) {
        Entry<K, V> newE = new Entry<>(key, value, null);
        table[hashKey] = newE;
        size++;
      } else {
        Entry<K, V> e = table[hashKey];
        while (e.key != null || e.key.equals(key)) {
          if (e.next == null) {
            Entry<K, V> newE = new Entry<>(key, value, table[hashKey]);
            table[hashKey] = newE;
            size++;
            break;
          } else {
            e = e.next;
          }
        }
        e.value = value;
      }
    }
  }

  @Override
  public V remove(Object key) {
    if (key == null) {
      if (table[0] == null) {
        return null;
      } else {
        Entry<K, V> tE = table[0];
        if (table[0].key == null) {
          Entry<K, V> keyToRemove = table[0];
          V vR = keyToRemove.value;
          table[0] = keyToRemove.next;
          size--;
          return vR;
        } else {
          Entry<K, V> prev = null;
          while (tE.key != null) {
            if (tE.next == null) {
              return null;
            } else {
              prev = tE;
              tE = tE.next;
            }
          }
          V vR = tE.value;
          prev.next = tE.next;
          size--;
          return vR;
        }
      }
    } else {
      int hashKey = hash(key.hashCode(), table.length);
      if (table[hashKey] == null) {
        return null;
      } else {
        Entry<K, V> tE = table[hashKey];
        if (table[hashKey].key.equals(key)) {
          Entry<K, V> keyToRemove = table[hashKey];
          V vR = keyToRemove.value;
          table[hashKey] = keyToRemove.next;
          size--;
          return vR;
        } else {
          Entry<K, V> prev = null;
          while (tE.key == null || !(tE.key.equals(key))) {
            if (tE.next == null) {
              return null;
            } else {
              prev = tE;
              tE = tE.next;
            }
          }
          V vR = tE.value;
          Objects.requireNonNull(prev).next = tE.next;
          size--;
          return vR;
        }
      }
    }
  }

  @Override
  public boolean containsKey(Object key) {
    if (key == null) {
      if (table[0] == null) {
        return false;
      } else {
        Entry<K, V> tE = table[0];
        while (tE.key != null) {
          if (tE.next == null) {
            return false;
          } else {
            tE = tE.next;
          }
        }
        return true;
      }
    } else {
      Entry<K, V> tE = table[hash(key.hashCode(), table.length)];
      if (tE == null) {
        return false;
      }
      while (tE.key == null || !(tE.key.equals(key))) {
        if (tE.next == null) {
          return false;
        } else {
          tE = tE.next;
        }
      }
      return true;
    }
  }

  @Override
  public boolean containsValue(Object value) {
    if (value == null) {
      for (var e : table) {
        while (e != null) {
          if (e.value == null) {
            return true;
          } else {
            e = e.next;
          }
        }
      }
    } else {
      for (var e : table) {
        while (e != null) {
          if (e.value == null) {
            e = e.next;
          } else if (e.value.equals(value)) {
            return true;
          } else {
            e = e.next;
          }
        }
      }
    }
    return false;
  }

  @Override
  public int size() {
    return 0;
  }

  void resize(int newCapacity) {
    if (table.length == MAX_CAPACITY) {
      threshHold = Integer.MAX_VALUE;
    } else {
      Entry<K, V>[] copyOfTable = Arrays.copyOf(table, table.length);
      @SuppressWarnings("unchecked")
      Entry<K, V>[] newHashTable = (Entry<K, V>[]) new Entry[newCapacity];
      table = newHashTable;
      size = 0;
      for (int i = 0; i < copyOfTable.length; i++) {
        if (copyOfTable[i] != null) {
          Entry<K, V> e = copyOfTable[i];
          while (e != null) {
            put(e.key, e.value);
            e = e.next;
          }
        }
      }
      threshHold = (int) (newCapacity * loadFactor);
    }
  }

  @Override
  public String toString() {
    StringBuilder result = new StringBuilder("{ ");
    for (var el : table) {
      if (el != null) {
        result.append(el).append(", ");
      }
    }
    int lastComma = result.lastIndexOf(",");
    if (lastComma > 1) {
      result.deleteCharAt(lastComma);
    }
    result.append("}");
    return result.toString();
  }

  static class Entry<K, V> {

    private final K key;
    Entry<K, V> next;
    private V value;

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

    public K getKey() {
      return key;
    }

    public V getValue() {
      return value;
    }

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

    @Override
    public boolean equals(Object o) {
      if (this == o) {
        return true;
      }
      if (o == null || getClass() != o.getClass()) {
        return false;
      }
      Entry<?, ?> entry = (Entry<?, ?>) o;
      return Objects.equals(key, entry.key) && Objects.equals(value, entry.value);
    }

    @Override
    public int hashCode() {
      return Objects.hash(key, value);
    }

    @Override
    public String toString() {
      return key + "=" + value;
    }
  }
}

Входные данные:

4 //количество пар
ng bi
tb zh
tj ym
vu ou
3 //количество запросов
tj
ng
vu

Выходные данные:

ym
ou
ou

Правильные выходные данные:

ym
bi
ou