在检查 hash-table 是否包含要删除的值后对其进行迭代有多好或多坏？

Question

我目前正在 HackerRank 上练习算法设计。

此问题与此处发现的挑战有关： https://www.hackerrank.com/challenges/ctci-ransom-note

我很快就解决了这个问题。但是，我运行遇到了一个让我很困扰的问题。我可以使用 contains(value) 函数检查散列 table 上的值。但是，我没有看到任何方法来检索与之关联的 key/keys。为了做到这一点，我被迫遍历 table 直到我再次找到那个值。

虽然我看到了哈希表的用处...但我认为我不会以最佳方式解决问题。如果我已经知道 table 包含我要删除的值，我觉得遍历 table 是浪费时间。

我的一个想法是制作两个 table 并让它们成为彼此的 "mirrored" 版本，因为在原始地图中使用数字作为键和副本或镜像map 使用键作为值。但是，这似乎不切实际，我觉得我只是缺少一些在我的哈希函数或其他知识中必不可少的东西。

我考虑这个的一个原因是我最近制作了一个使用 sqllight table 来保存数据的程序。我只需要一个循环来搜索和删除这些值，这样效率更高不是吗？

我可以解释一下如何更好地实现我下面的代码的功能吗？

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  int m = in .nextInt();
  int n = in .nextInt();
  String isTrue = "Yes";
  Hashtable myTable = new Hashtable();
  String magazine[] = new String[m];

  for (int magazine_i = 0; magazine_i < m; magazine_i++) {
   myTable.put(magazine_i, in .next());
  }

  Set < Integer > keySet = myTable.keySet();

  for (int ransom_i = 0; ransom_i < n; ransom_i++) {
   String temp = in .next();
   //System.out.println("Line " + ransom_i);
   if (!myTable.containsValue(temp)) {

    isTrue = "No";
    break;
   } else {
    for (int key: keySet) {
     if (myTable.get(key).equals(temp)) {
      myTable.remove(key);
      //System.out.println("Found it");
      break;
     }
    }
   }
  }
  System.out.println(isTrue);

 }
}

Answer 1

这是一个简单的方法：

public class DenyReturn<K,T> extends Map<K,T>{
  private Map m;
  private List<T> dontreturn;
  public DenyReturn(Map<K,T> m, List<T> dontreturn) {
    this.m = m;
    this.dontreturn = dontreturn;
  }

  public T get(Object key) {
    T val = super.get(key);
    if (dontreturn.contains(val)) return null;
    return val;
  }

  //implement all other methods of Map by invoking the inner map methods
}

在检查 hash-table 是否包含要删除的值后对其进行迭代有多好或多坏？

How good or bad is it to iterate over a hash-table after checking that it contains a value you want to remove?

java

algorithm

hashtable