StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Assuming you need speed without the overhead of the <code>*Set</code> classes, then you could write <code>H</code> as follows:</p> <pre><code>/** * Hashes a set of integers. * * @param list to hash * @return hash code */ public static int H(int list[]) { // XOR all the integers together. int hashcode = 0; for (int val : list) { hashcode ^= val; } return hashcode; } </code></pre> <p>It is the same regardless of the order, and it is relatively efficient.</p> <p>For example:</p> <pre><code>public static void main(String[] args) { System.out.println(Integer.toHexString(H(new int[]{0xabcd,0x1234,0x1111}))); System.out.println(Integer.toHexString(H(new int[]{0x1234,0x1111,0xabcd}))); } </code></pre> <p>Displays:</p> <pre><code>a8e8 a8e8 </code></pre> <p>This could be generalized to more than just <code>int</code>s by doing the following:</p> <pre><code>/** * Hashes a set of objects. * * @param list to hash * @return hash code */ public static int H(Object list[]) { // XOR all the hashes together. int hashcode = 0; for (Object val : list) { hashcode ^= val.hashCode(); } return hashcode; } </code></pre> <p>The <code>main</code> program would then have to use arrays of <code>Integer</code> instead of the primitive <code>int</code>. </p> <p>Adding the numbers should be almost as quick, and might give you a better distribution over the 32 bit range. If the elements of the set are already uniformly distributed over the range, then xor might be better.</p> <p>However, with both methods, you can manufacture collisions easily with integers. For example, with the adding method;</p> <pre><code>{1000, 1001, 1002} {0, 1, 3002} </code></pre> <p>Both of these arrays have the same <code>H()</code>.</p> <p>With the XOR method;</p> <pre><code>{0x1010, 0x0101} {0x1111, 0x0000} </code></pre> <p>Both of these have the same <code>H()</code>. </p> <p>Similarly, the <code>0</code> element is problematic since lists will have the same hash with or without it. You can mitigate this by adding a constant value at each iteration. For example:</p> <pre><code> ... hashcode += val.hashCode() + CONSTANT; ... </code></pre> <p>Or by including the number of elements as the initial hash code:</p> <pre><code> ... // XOR all the hashes together. int hashcode = list.length; ... </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload