Java - Use hashcode to compare string pairs

最近在分析資料表時需要filter相似的資料，並且留下兩筆之中以時間為最新的一筆。

關於相似的定義是在於：

假設一資料表的定義為

Pair1, Pair2, UpdateTime (Pair1, Pair2為primary key)

實際資料可能為

X1234, C1456, 2012/09/23
C1456, X1234, 2010/08/11
.....

在第一筆及第二筆之X1234, C1456與C1456, X1234及視為同一種情況，依據time來捨棄其一。

當然還有很多組，又或者有些不會有這種請況，則就不用捨棄囉！

本來是先利用SQL語法撈取所有的資料，再利用SQL語法去過濾！如下：

select * from table where Pair1 = '"+pair2+"' and Pair2 = '"+paor1+"';

利用取出的一筆再去查詢資料表該筆是否有此一請況！

雖然是寫的出來，但是方法不太妥！

因此就想到說A -> B, B->A兩者若利用其hashcode相加的話不就會一樣？

不過利用這個方法需要注意的是，假設X1234, C1456之hashcode總和為234123412

難免會有其他組之hashcode總和會跟他一樣的，但兩組是八竿子沒相關的，事實是真的有！

因此，我就定義了Map

Map<Integer, Map<String, String>> pairFilter = new HashMap<Integer, Map<String, String>>();

Integer是存放hashcode為key值，對映的是另一個Map，另一個Map是存放key是pair

如："X1234, C1456"，其value為time!!

如此若碰到hashcode總和一樣的pair，如"X1234, C1456"  and  "C5434, D3456"

就可以一起存放至Map<String, String>，以同一hashcode之key與之對映！

作法上會稍微複雜一點，比起再去查詢SQL如此直觀的想法，但少用到database來操作

總是比較快，更何況資料不是百筆，而可能是數萬筆！

  1. while(rs.next()){
  2.       pair1 = rs.getString("Pair1");
  3.       pair2 = rs.getString("Pair2");
  4.       updateTime = rs.getString("Updatetime");
  5.       int hashcodePair = pair1.hashCode()+pair2.hashCode();
  6.       if(!pairFilter.containsKey(hashcodePair)){
  7.          Map data = new HashMap();
  8.          data.put(pair1+","+pair2, updateTime);
  9.          pairFilter.put(hashcodePair, data);
  10.       }else{
  11.          //hashcode total same. ex: A->B, B->A or just total same
  12.          Map check = pairFilter.get(hashcodePair);
  13.          if(check.containsKey(pair2+","+pair1)){
  14.             SimpleDateFormat dateformat = new SimpleDateFormat("yyyy/MM/dd");
  15.             java.util.Date date1 = dateformat.parse(check.get(pair2+","+pair1));
  16.             java.util.Date date2 = dateformat.parse(updateTime);
  17.             if(date1.before(date2)){
  18.                check.remove(pair2+","+pair1);
  19.                check.put(pair1+","+pair2, updateTime);
  20.                pairFilter.put(hashcodePair, check);
  21.             }
  22.          }else{
  23.             check.put(pair1+","+pair2, updateTime);
  24.             pairFilter.put(hashcodePair, check);
  25.          }
  26.      }
  27.   }

上述為建立pairfilter variable的程式，一開始之while(rs.next())為run該資料表下所有的資料，

首先先檢查if(!pairFilter.containsKey(hashcodePair)) 此key是否已存在了，沒有的話就建立它

所對映value，即另一Map。再來若該key值已存在，則很有可能碰到兩種情況：

一、B->A出現了

利用check.containsKey(pair2+","+pair1)判斷

若是B->A則接下來是判斷它們的time來決定要留誰

二、剛好hashcode加總相等

若是加總相等的，則將Map check = pairFilter.get(hashcodePair);之check再put進一組資料即可！

 如此一來就大功告成！接下來就不列出print pairFilter的過程！

方法二：

後來在無意中又要比較A->B, B->A則一的問題，發現我上面的方法是利用

Map<Integer, Map<String, String>> pairFilter = new HashMap<Integer, Map<String, String>>();

來filter，現在我改成了宣告兩個變數來處理這一個問題。

Set<Integer> hashcodeSet = new HashSet<Integer>();  //紀錄pair的hashcode
Map<String, String> pairsFilter = new HashMap<String, String>(); //pairs -> key, updatetime->value

修改後的程式如下：

  1. while(rs.next()){
  2.    pair1 = rs.getString("Pair1");
  3.    pair2 = rs.getString("Pair2");
  4.    updateTime = rs.getString("Updatetime");
  5.    if(!hashcodeSet.contains(pair1.hashCode()+pair2.hashCode())){
  6.       hashcodeSet.add(pair1.hashCode()+pair2.hashCode());
  7.       pairsFilter.put(pair1+","+pair2, updateTime);
  8.    }else{
  9.       if(pairsFilter.containsKey(pair2+","+pair1)){
  10.          SimpleDateFormat dateformat = new SimpleDateFormat("yyyy/MM/dd");
  11.          java.util.Date date1 = dateformat.parse(pairsFilter.get(pair2+","+pair1)); java.util.Date date2 = dateformat.parse(updateTime);
  12.          if(date1.before(date2)){
  13.             pairsFilter.remove(pair2+","+pair1);
  14.          }
  15.          pairsFilter.put(protein1+","+protein2, updateTime);
  16.       }
  17.    }
  18. }

修改後的程式變的比較單純，利用hashcodeSet幫忙把關，若碰到加總一樣的hashcode，

有兩種可能，一個是B->A出現了，若非B->A則就是新的一對pair，因此就加到pairsFilter內，

想法變得比較單純一點。

方法三：

近期在這個問題上找到比較簡單的判斷法(學妹提供)，只要保留一個HashMap即可

相關程式碼如下：

  1. while(rs.next()){
  2.     protein1 = rs.getString("Protein1");
  3.     protein2 = rs.getString("Protein2");
  4.     updateTime = rs.getString("Updatetime");
  5.     if(!pairsFilter.containsKey(protein2+","+protein1)){
  6.         pairsFilter.put(protein1+","+protein2, updateTime);
  7.     }else{
  8.         SimpleDateFormat dateformat = new SimpleDateFormat("yyyy/MM/dd");
  9.         java.util.Date date1 = dateformat.parse(pairsFilter.get(protein2+","+protein1));
  10.         java.util.Date date2 = dateformat.parse(updateTime);
  11.         if(date1.before(date2)){
  12.            pairsFilter.remove(protein2+","+protein1);
  13.            pairsFilter.put(protein1+","+protein2, updateTime);
  14.         }
  15.     }
  16. }
首先，當第一筆資料進入檢查時，找尋B -> A是否存在，若不存在則A->B例子就可大大

方方的put，當真正的B->A出現時，就會與之前的A->B碰撞，此時只要彼此比較更新時間

就可以取得誰才有生存權！

由於不清楚A->B, B->A那個會先出現，因此設了一個Set來存Hashcode，其實只要先顛倒

自己的順序就可以清楚知道另一個配對是否出現了，只能說想太多了orz...

總結來說，當初將問題想的過於複雜，導致之前的作法有多餘的檢查！

留言

張貼留言