Hash Functions - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:27:29Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:27, 9 October 2019
Line 144:		Line 144:
	The code:		The code:

	Link to git.charlesreid1.com: https://charlesreid1.com~~:3000~~/cs/java/src/master/hash/BuiltinHashFunction.java		Link to git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/hash/BuiltinHashFunction.java

	<pre>		<pre>

Admin: /* What Hash Function Does HashMap Use? */

2017-06-29T07:58:34Z

What Hash Function Does HashMap Use?

← Older revision		Revision as of 07:58, 29 June 2017
Line 130:		Line 130:


			==Finding Collisions for Built-In Hash Function==

			To test how good the hash function built into the HashMap class is, I wrote a short class that would load a large number of strings (7,000) from a file, and compute a hash for each, counting the duplicates. First, the output - then the code.

			The output:

			<pre>
			$ javac BuiltinHashFunction.java && java BuiltinHashFunction

			Builtin Hash Function: Hash codes: 7144 Collisions: 3
			</pre>

			The code:

			Link to git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/hash/BuiltinHashFunction.java

			<pre>
			mport java.util.Random;
			import java.util.List;
			import java.util.ArrayList;
			import java.util.Set;
			import java.util.HashSet;
			import java.util.Scanner;
			import java.io.FileReader;
			import java.io.BufferedReader;
			import java.io.FileNotFoundException;

			public class BuiltinHashFunction {
			public static void main(String[] args) throws FileNotFoundException {
			//shortTest();
			manyCollisions();
			}


			public static void manyCollisions() throws FileNotFoundException {

			Scanner s = new Scanner(new BufferedReader(new FileReader("14oxenofthesun.txt")));

			// Populate word list
			Set<String> wordset = new HashSet<>();
			while(s.hasNext()) {
			wordset.add(s.next());
			}

			List<Integer> list = new ArrayList<>();
			Set<Integer> set = new HashSet<>();
			for(String word : wordset) {
			int next = hash(word.hashCode());
			list.add(next);
			set.add(next);
			}
			int diff = list.size() - set.size();
			System.out.printf("Builtin Hash Function: \tHash codes: %d\t\tCollisions: %d\n", list.size(), diff);
			}



			public static void shortTest() {
			int n = 100;
			for(int i=0; i<n; i++) {
			String s = randomString();
			System.out.println(s);
			System.out.println(s.hashCode());
			System.out.println(hash(s.hashCode()));
			System.out.println();
			}
			}

			public static String randomString() {
			Random r = new Random();
			char[] rand = new char[2+r.nextInt(7)];
			for(int i=0; i<rand.length; i++) {
			rand[i] = (char)('A' + r.nextInt(26));
			}
			return new String(rand);
			}

			public static int hash(int h) {
			// This function ensures that hashCodes that differ only by
			// constant multiples at each bit position have a bounded
			// number of collisions (approximately 8 at default load factor).
			h ^= (h >>> 20) ^ (h >>> 12);
			return h ^ (h >>> 7) ^ (h >>> 4);
			}

			}
			</pre>

	==Flags==		==Flags==

Admin: /* Flags */

2017-06-29T06:56:16Z

Flags

← Older revision		Revision as of 06:56, 29 June 2017
Line 57:		Line 57:

	Therefore, the distribution of data can have an affect on the hash function and make different hash functions better or worse choices. Ultimately it is important to test your hash function of interest on your data set of interest.		Therefore, the distribution of data can have an affect on the hash function and make different hash functions better or worse choices. Ultimately it is important to test your hash function of interest on your data set of interest.

			==What Hash Function Does HashMap Use?==

			You may be wondering what hash function the HashMap class in the Java Collections API uses. We can take a look at the [[OpenJDK]] source code for this class here: https://github.com/openjdk/jdk7-jdk/blob/master/src/share/classes/java/util/HashMap.java

			In particular, shortly after the constructors, on line 264, the hash function is defined: https://github.com/openjdk/jdk7-jdk/blob/master/src/share/classes/java/util/HashMap.java#L264

			As the comment states, this hash function is applied to the object's built-in hashCode result, and not to the object itself.

			<pre>
			/**
			* Applies a supplemental hash function to a given hashCode, which
			* defends against poor quality hash functions. This is critical
			* because HashMap uses power-of-two length hash tables, that
			* otherwise encounter collisions for hashCodes that do not differ
			* in lower bits. Note: Null keys always map to hash 0, thus index 0.
			*/
			static int hash(int h) {
			// This function ensures that hashCodes that differ only by
			// constant multiples at each bit position have a bounded
			// number of collisions (approximately 8 at default load factor).
			h ^= (h >>> 20) ^ (h >>> 12);
			return h ^ (h >>> 7) ^ (h >>> 4);
			}
			</pre>

			Immediately after the hash function is the indexFor function, which is used to transform a hash code in a table into an array index, the critical mapping step:

			<pre>
			/**
			* Returns index for hash code h.
			*/
			static int indexFor(int h, int length) {
			return h & (length-1);
			}
			</pre>

			Finally, these methods come together in the get() method of the HashMap, which is defined shortly after on line 314: https://github.com/openjdk/jdk7-jdk/blob/master/src/share/classes/java/util/HashMap.java#L314

			<pre>
			/**
			* Returns the value to which the specified key is mapped,
			* or {@code null} if this map contains no mapping for the key.
			*
			* <p>More formally, if this map contains a mapping from a key
			* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
			* key.equals(k))}, then this method returns {@code v}; otherwise
			* it returns {@code null}. (There can be at most one such mapping.)
			*
			* <p>A return value of {@code null} does not <i>necessarily</i>
			* indicate that the map contains no mapping for the key; it's also
			* possible that the map explicitly maps the key to {@code null}.
			* The {@link #containsKey containsKey} operation may be used to
			* distinguish these two cases.
			*
			* @see #put(Object, Object)
			*/
			public V get(Object key) {
			if (key == null)
			return getForNullKey();
			int hash = hash(key.hashCode());
			for (Entry<K,V> e = table[indexFor(hash, table.length)];
			e != null;
			e = e.next) {
			Object k;
			if (e.hash == hash && ((k = e.key) == key \|\| key.equals(k)))
			return e.value;
			}
			return null;
			}
			</pre>



	==Flags==		==Flags==

Admin: /* Other Notes on Hash Functions */

2017-06-29T06:48:07Z

Other Notes on Hash Functions

← Older revision		Revision as of 06:48, 29 June 2017
Line 45:		Line 45:


	~~==Other Notes on Hash Functions==~~

	===Minimal Perfect Hashing===		===Minimal Perfect Hashing===

Admin: /* Perfect Hashing */

2017-06-25T23:05:38Z

Perfect Hashing

← Older revision		Revision as of 23:05, 25 June 2017
Line 36:		Line 36:

	(If the map were a function, we would say the function is a one-to-one function.)		(If the map were a function, we would say the function is a one-to-one function.)


			===Cyclic Permutation Hash Function===

			Also see [[Hash Functions/Cyclic Permutation]]

			The cyclic permutation hash function reduces data to a binary representation, then cycles through the digits, for example shifting 10011 two digits to the right results in 11100.


			==Other Notes on Hash Functions==

	===Minimal Perfect Hashing===		===Minimal Perfect Hashing===

Admin at 22:34, 25 June 2017

2017-06-25T22:34:20Z

← Older revision		Revision as of 22:34, 25 June 2017
Line 4:		Line 4:

	Non-cryptographic hash functions are mainly used for mapping keys to values, so a collision is an inconvenience rather than a problem.		Non-cryptographic hash functions are mainly used for mapping keys to values, so a collision is an inconvenience rather than a problem.

			==Non-Crypto Hash Functions==

			===Trivial Hash Functions===

			Trivial hash functions use the data itself as the hash value. This works if the data are small in value or limited in length. (Example: hashing integers below 100. Can just use the integers themselves as their own index in the hash collection.)

			===Checksums===

			For longer sequences of data, be they strings or bytes, the approach is to break the sequence into small parts, and to make the output dependent on each piece, and each piece dependent on the others. This can be done with an iterative algorithm that maintains a "state" (integer or set of integers) modified by each chunk of the stream.

			For example:

			<pre>
			# Start by initializing the state
			S = S0

			# For each piece of data,
			for k in range(1,m):
			# fold the current chunk of data into the state
			S = modifyHash(S, b[k])
			# Extract the hash value from the state
			return returnHash(S, n)
			</pre>



			===Perfect Hashing===

			Perfect hash functions, as indicated by the term "perfect," fulfill everything that hash functions must do. Specifically, perfect hash functions are '''injective''' and map each valid input to a different valid output.

			(If the map were a function, we would say the function is a one-to-one function.)

			===Minimal Perfect Hashing===

			A minimal perfect hash maps every valid input to a different valid output, but do so in a way that requires minimal space, so that all of the outputs are consecutive.

			A minimal perfect hash is very challenging to find.

			===Avoiding Collisions===

			If you're using a simpler hash function, it is possible to determine the effect that similar inputs will have on the output. For example, if hashing phone numbers, most of the leading digits will be similar. Any method that depends heavily on the leading digits is likely to lead to higher collisions.

			Therefore, the distribution of data can have an affect on the hash function and make different hash functions better or worse choices. Ultimately it is important to test your hash function of interest on your data set of interest.

			==Flags==

			{{MapsFlag}}

			[[Category:Maps]]

Admin: Created page with "Hash functions have two principal applications: cryptographic hash functions, and non-cryptographic hash functions. Cryptographic hash functions must have a much lower probab..."

2017-06-25T11:13:22Z

Created page with "Hash functions have two principal applications: cryptographic hash functions, and non-cryptographic hash functions. Cryptographic hash functions must have a much lower probab..."

New page

Hash functions have two principal applications: cryptographic hash functions, and non-cryptographic hash functions.

Cryptographic hash functions must have a much lower probability of collision, since a collision could result in identity theft or forged documents.

Non-cryptographic hash functions are mainly used for mapping keys to values, so a collision is an inconvenience rather than a problem.