how to shuffle key-value pairs?

问题:

I have a set of values which need to be shuffled when needed. I don't know which variable type is best for me. Data is actually based on key-value structure.Like;

100 "white"
200 "black"
300 "red"

and like that. What I want to do is to change the key-value pairs according to I don't know yet, some algorithm.But they need to be shuffled like this, but shuffling need to be not random, so I can revert data when I need.

100 "red"
200 "white"
300 "black"

I don't really know how my approach should be to the solution. Should I use HashTable or something, and how can I shuffle them dynamically? Any help is appreciated

回答1:

Another way for shuffling the key-value mappings randomly:

public static <K,V> void shuffleMap(Map<K,V> map) {
    List<V> valueList = new ArrayList<V>(map.values());
    Collections.shuffle(valueList);
    Iterator<V> valueIt = valueList.iterator();
    for(Map.Entry<K,V> e : map.entrySet()) {
        e.setValue(valueIt.next());
    }
}

---

Edit:

If you don't want to change the original map (since you need it afterwards), you can create a new one instead:

public static <K,V> Map<K,V> shuffleMap(Map<K,V> map) {
    List<V> valueList = new ArrayList<V>(map.values());
    Collections.shuffle(valueList);
    Iterator<V> valueIt = valueList.iterator();
    Map<K,V> newMap = new HashMap<K,V>(map.size());
    for(K key : map.keySet()) {
        newMap.put(key, valueIt.next());
    }
    return newMap;
}

You do not really want a seemingly-randomly mixing which can be reverted (which quickly gets complicated), but simply retain your original map. If this does not fit, you need to describe your problem better.

---

Okay, you want to encrypt the mapping by using a secret key, giving another mapping, and then decrypt it again. Obviously random shuffling does not help here, and even pseudorandom is no good, since it gives no reliable way to reshuffle. In the basic case, your key would be a invertible map between the keys of our mapping.

public static <K,V> Map<K,V> encryptMap(Map<K,V> plainMap, Map<K,K> key) {
    Map<K,V> cryptoMap = new HashMap<K,V>(plainMap.size());
    for(Map.Entry<K,V> entry : plainMap.entrySet()) {
       cryptoMap.put(key.get(entry.getKey()), entry.getValue());
    }
    return cryptoMap;
}

Decryption works the same, in fact, only using the reverse map of the key.

So, when you have your example keys of {100, 200, 300}, any permutation of these keys is a valid key for our "encryption scheme". (There are only 6 possible ones, which is not very secure.)

Map sampleKey = new HashMap<Integer, Integer>();
sampleKey.put(100, 200);
sampleKey.put(200, 300);
sampleKey.put(300, 100);

Map sampleUnKey = new HashMap<Integer, Integer>();
for(Map.Entry<Integer, Integer> e : sampleKey) {
   sampleUnKey.put(e.getValue(), e.getKey());
}

Map<Integer, String> data = new HashMap<Integer, String>();
data.put(100, "white");
data.put(200, "black");
data.put(300, "red");

System.out.println(data);

Map<Integer, String> encrypted = encryptMap(data, sampleKey);

System.out.println(encrypted);

Map<Integer, String> decrypted = encryptMap(data, sampleUnKey);

System.out.println(decrypted);

The map decrypted now should be the same as the original map.

For bigger keysets you would want to find a scheme to get a suitable permutation of keys from some input-able key.

回答2:

It looks like you need a list of tupples. A Map is exactly that. However, a standard like HashMap has no functionality for changing the relationship between key and value.

I think I would have implemented my own Map for this. Create a class that implements java.util.Map, implement the required methods and create some other methods for "mixing".

It all dependes on what functionality you really need on the list of tupples. Do you need to look up colors very fast? Can there be more than one tupple with the same numbers?

回答3:

I am not sure how exactly you are going to shuffle the pairs, but if you need to shuffle them based on the key, you can use a Map:

Map<String, String> map = new HashMap<String, String>();
map.put("100", "white");
map.put("200", "black");
map.put("300", "red");

// swap 100 with 200
String temp = map.get("100");
map.put("100", map.get("200"));
map.put("200", temp);

Alternatively, if you need to shuffle the pair randomly, you can create a class Pair (which will basically store an int and a String), as suggested by larsmans, and store them in an array. Then, a slightly-modified version of Fisher-Yates shuffle can be used. Something along these lines:

// initialize list
List<Pair<Integer, String>> values = new ArrayList<Pair<Integer, String>>();
values.add(new Pair<Integer, String>(100, "white"));
values.add(new Pair<Integer, String>(200, "black"));
values.add(new Pair<Integer, String>(300, "red"));

// shuffle
System.out.println(values); // e.g., [100 white, 200 black, 300 red]
Random random = new Random();
for (int i = values.size() - 1; i > 1; i--) {
    int j = random.nextInt(i + 1);
    // swap values between i-th Pair and j-th Pair
    Pair<Integer, String> iPair = values.get(i); // the iPair :-)
    Pair<Integer, String> jPair = values.get(j);
    String iString = iPair.getSecond();
    iPair.setSecond(jPair.getSecond());
    jPair.setSecond(iString);
}
System.out.println(values); // e.g., [100 red, 200 black, 300 white]