1
\$\begingroup\$

I am trying to implement feature hashing in Java. For this I am trying to use Hashing functions from guava.

This is how I am doing it now:

//seed is any integer.
HashFunction hf = Hashing.murmur3_32(seed); 

//key is the input int and hd is the hashed dimension.
int hash = Hashing.consistentHash(hf.hashInt(key), hd);

I have another method for sign, not shown in this question.

To measure the performance, I am doing something like below:

int min = 0, max = 2000000, sampleSize = 3000000;
int[] hds = { 2000, 5000, 6000, 10000, 20000, 500000, 1000000, 2000000 };

List<Double> guavaCollisons = new ArrayList<>();

UniformIntegerDistribution runif = new UniformIntegerDistribution(min, max);

Arrays.stream(hds)
        .forEach(hd -> {
            int seed = runif.sample();

            HashFunction hf = Hashing.murmur3_32(seed);

            Map<Integer, Set<Integer>> guava = new HashMap<>();

            Arrays.stream(runif.sample(sampleSize))
                    .forEach(key -> {

                        int guavaHash = Hashing.consistentHash(hf.hashInt(key), hd);

                        if (!guava.containsKey(guavaHash))
                            guava.put(guavaHash, new HashSet<Integer>());

                        guava.get(guavaHash).add(key);
                    });

            double guavaCollisionHd = guava.entrySet()
                    .stream()
                    .mapToInt(entry -> entry.getValue()
                            .size())
                    .average()
                    .getAsDouble();

            guavaCollisons.add(guavaCollisionHd);

            System.out.println("Available buckets = " + hd 
                + ",  unutilized = " + (hd - guava.keySet().size())
                + ", guava collision = " + guavaCollisionHd);
        });

double guavaCollision = Stats.meanOf(guavaCollisons);
System.out.println("Average collision = " + guavaCollision);

My questions are:

  1. Is this a correct way to implement the 'hash' part of feature hashing?
  2. Is this a correct way to measure the collision rate of the hashing technique?
\$\endgroup\$
  • \$\begingroup\$ If you are downvoting, please provide reason; otherwise I can't improve the quality of this question. \$\endgroup\$ – Sayan Pal Mar 11 '17 at 7:56
1
\$\begingroup\$

Simplified code:

List<Double> guavaCollisions = Arrays.stream(hashDimensions)
    .map(dimension -> {
        HashFunction hashFunction = Hashing.murmur3_32(runif.sample());
        Map<Integer, Long> guavaCounts = Arrays.stream(runif.sample(sampleSize))
            .collect(Collectors.groupingBy(key -> Hashing.consistentHash(hashFunction.hashInt(key), dimension),
                 Collectors.counting());
        return guavaCounts.values().stream().mapToLong(id -> id).average().getAsDouble();
    }).collect(Collectors.toList());

Reasoning:

  • Inlined the seed. Keeping the seed variable there isn't necessary since we don't use it anymore, not even in the logging-statement.

  • Used collect instead of forEach(el -> collection.add(el)) to create Collections which is more idiomatic.

  • Dropped the Set<Integer> from the Map, since we don't actually ever use the Integers we keep in memory here, but instead only want the number of unique integers. (Note that currently I don't check for uniqueness, which means the semantics changed)

  • Simplified the calculation of average from guavaCounts by not streaming the entry-set and then mapping to value, which could be simplified by using Entry::getValue, but directly streaming the values().

  • Dropped the System.out because it's incredibly slow in comparison, a side-effect that shouldn't be happening in a Stream and doesn't add viable information to the "final" result of the code.

  • Renamed hds, hd and hf because shortening names is pointless. I'd have preferred to also rename runif, but didn't find a better name, which would remain succinct.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.