文章目录

说明

《数据结构与算法分析-java语言描述》，有个对比ASCII计算的String的HashCode。

书上的方法1：

private int hashFunction1(String sc , int sizeTable) {
		int hashVal = 0;
		char[] cs = sc.toCharArray();
		for (char c : cs) {
			hashVal += c;
		}
		return hashVal % sizeTable;
	}

书上的方法2 ：Horner法则

/** * Horner法则 * 像极了java自带的方法 * */
	private Integer hashFunction2(String sc, int tableSize) {
		int hashVal = 0;
		//计算 值
		for(int i=0 ; i < sc.length() ; i++) {
			hashVal = 37*hashVal + sc.charAt(i);
		}
		//转换成存入位置
		hashVal %= tableSize ;
		//避免引进负数？？目的？
		if(hashVal<0) {
			hashVal+=tableSize ; 
		}
		return hashVal;
	}

String的方法：

 /** * Returns a hash code for this string. The hash code for a * {@code String} object is computed as * <blockquote><pre> * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] * </pre></blockquote> * using {@code int} arithmetic, where {@code s[i]} is the * <i>i</i>th character of the string, {@code n} is the length of * the string, and {@code ^} indicates exponentiation. * (The hash value of the empty string is zero.) * * @return a hash code value for this object. */
    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

测试一下，和java自带的hashCode差距大吗。

测试代码

package cn.edut.com.tarena;


import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeSet;

import org.junit.Test;

public class Demo05_Hash1  {
	@Test
	public void test001() {
		String s = "Whenever it is invoked on the same object more than once during\r\n"
				+ " * an execution of a Java application, the {@code hashCode} method\r\n"
				+ " * must consistently return the same integer, provided no information\r\n"
				+ " * used in {@code equals} comparisons on the object is modified.\r\n"
				+ " * This integer need not remain consistent from one execution of an\r\n"
				+ " * application to another execution of the same application.\r\n"
				+ " * <li>If two objects are equal according to the {@code equals(Object)}\r\n"
				+ " * method, then calling the {@code hashCode} method on each of\r\n"
				+ " * the two objects must produce the same integer result.\r\n"
				+ " * <li>It is <em>not</em> required that if two objects are unequal\r\n"
				+ " * according to the {@link java.lang.Object#equals(java.lang.Object)}\r\n"
				+ " * method, then calling the {@code hashCode} method on each of the\r\n"
				+ " * two objects must produce distinct integer results. However, the\r\n"
				+ " * programmer should be aware that producing distinct integer results\r\n"
				+ " * for unequal objects may improve the performan";
		String[] ss = s.split("\\s+");
		// 存 java 自带 hashcode
		HashMap<Integer, TreeSet<String>> hashMap0 = new HashMap< >();
		// 存 函数1 hashcode
		HashMap<Integer, TreeSet<String>> hashMap1 = new HashMap<>();
		// 存函数2 hashcode
		HashMap<Integer, TreeSet<String>> hashMap2 = new HashMap<>();
		/* * 计算hashcode 存入map */
		for (String sc : ss) {
			int tableSize = 10007;
			saveMap(hashMap0,  hashFunction0(sc) , sc);
			saveMap(hashMap1, hashFunction1(sc , tableSize), sc);
			saveMap(hashMap2, hashFunction2(sc , tableSize), sc);

		}
		/* * 如果重复就打印出来 */
		System.out.println("系统的hashCode分布：");
		showIfCrash(hashMap0);
		System.out.println("我的hashCode分布：");
		showIfCrash(hashMap1);
		System.out.println("Horner法则：");
		showIfCrash(hashMap2);

	}


	private void saveMap(HashMap<Integer, TreeSet<String>> hashMap1, Integer hashVal , String s ) {
		if (hashMap1.get(hashVal) != null) {
			hashMap1.get(hashVal).add(s);
		} else {
			TreeSet<String> treeSet = new TreeSet<>();
			treeSet.add(s);
			hashMap1.put(hashVal, treeSet) ; 
		}
	}

	private <K, V > void showIfCrash(HashMap<K,TreeSet<V>> hashMap1) {

		Set<Entry<K, TreeSet<V>>> entrySet= hashMap1.entrySet();
		for (Entry<K, TreeSet<V>> e : entrySet) {
			if(e.getValue().size()>1) {
				System.out.println(e.getKey() + " : " + e.getValue());
			}
		}
	}

	/** * java自带方法 * public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; } */
	private int hashFunction0(String cs) {
		return cs.hashCode();
	}
		
	/** * 算法1： * 把字符串字符的ASCII码加起来。 * 对 tableSize 的依赖大 */
	private int hashFunction1(String sc , int tableSize) {
		int hashVal = 0;
		char[] cs = sc.toCharArray();
		for (char c : cs) {
			hashVal += c;
		}
		return hashVal%tableSize;
	}
	
	
	/** * Horner法则 * 像极了java自带的方法 * */
	private Integer hashFunction2(String sc, int tableSize) {
		int hashVal = 0;
		//计算 值
		for(int i=0 ; i < sc.length() ; i++) {
			hashVal = 37*hashVal + sc.charAt(i);
		}
		//转换成存入位置
		hashVal %= tableSize ;
		//避免引进负数？？目的？
		if(hashVal<0) {
			hashVal+=tableSize ; 
		}
		return hashVal;
	}
	
	
}

测试结果

String.hashCode源码分析

https://blog.csdn.net/weixin_43145361/article/details/97802510