Posted in Java, 技术

Java 基础:hashCode方法

Writer:BYSocket(泥沙砖瓦浆木匠)

微博:BYSocket

豆瓣:BYSocket

一、前言

    泥瓦匠最近被项目搞的天昏地暗。发现有些要给自己一些目标,关于技术的目标:

专注很重要。专注Java 基础 + H5(学习)

    其他操作系统,算法,数据结构当成课外书博览。有时候,就是那样你越是专注方面越多对自己打击越大学啥啥都不好。今天带来Java基础:hashCode方法

二、hashCode方法

    hash code(散列码,也可以叫哈希码值)是对象产生的一个整型值。其生成没有规律的。二者散列码可以获取对象中的信息,转成那个对象的“相对唯一”的整型值。所有对象都有一个散列码,hashCode()是根类 Object 的一个方法。散列表的工作原理在Java基础不展开讲,只要知道它是一种快速的“字典”即可。下面引用老外一张图:

三、两个小例子

    首先泥瓦匠引用一段来自 Object规范 【JavaSE6】:

hashCode的常规协定是:

            • 1、在 Java 应用程序执行期间,在对同一对象多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是将对象进行 equals 比较时所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需保持一致。
  • 2、如果根据 equals(Object) 方法,两个对象是相等的,那么对这两个对象中的每个对象调用 hashCode 方法都必须生成相同的整数结果。
    • 3、如果根据equals方法,两个对象不相等,那么对这两个对象中的任一对象上调用 hashCode 方法 要求一定生成不同的整数结果。但是,程序员应该意识到,为不相等的对象生成不同整数结果可以提高哈希表的性能。
  •     由于hashCode定义在根类Object,所以每个对象都是Object,都具有一个默认的散列值,即是对象的存储地址。泥瓦匠请大家看一下这个例子:
public class HashCodeTest
{
	public static void main(String[] args)
	{
		String s = "hashCode";
		StringBuilder sb = new StringBuilder(s);
		System.out.println("hashCode1: " + s.hashCode() + " " + sb.hashCode());
		
		String s1 = new String("hashCode");
		StringBuilder sb1 = new StringBuilder(s1);
		System.out.println("hashCode2: " + s1.hashCode() + " " + sb1.hashCode());
		
		// are they equals?
		System.out.println("s  s1 : " + s.equals(s1));
		System.out.println("sb sb1: " + sb.equals(sb1));
	}
}

   run 一下,可以在控制台看到:

hashCode1: 147696667 1385112968
hashCode2: 147696667 870919696
s  s1 : true
sb sb1: false

   泥瓦匠小结

1、s 与 s1相等,且hashCode一样。验证了【hashCode的常规协定】的第二条。原因是字符串的散列码由内容导出的。(这个第二个例子我们会验证)

2、StringBuilder 里面没有定义hashCode方法,所以导出的是Object默认的对对象存储的地址。(注意到Object的hashCode方法前面有个native的修饰符,这表示hashCode方法是由非java语言实现的,具体的方法实现在外部,返回内存对象的地址。)详情请看认识&理解关键字 native 实战篇

    泥瓦匠刚刚提到字符串散列码是由内容导出的。下面看看String的hashCode的实现。

       /** The value is used for character storage */
	private char value[];
	
	private int hash;// Default to 0
	
    /**
     * Returns a hash code for this string. The hash code for a
     * String object is computed as
     * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
     */
	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;
	}

    泥瓦匠小结

1、s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]  数学公式代表什么?

s[i]是string的第i个字符,n是String的长度。31为啥呢?下面引用《Effective Java》的原话:

之所以选择31,是因为它是个奇素数,如果乘数是偶数,并且乘法溢出的话,信息就会丢失,因为与2相乘等价于移位运算。使用素数的好处并不是很明显,但是习惯上都使用素数来计算散列结果。31有个很好的特性,就是用移位和减法来代替乘法,可以得到更好的性能:31*i==(i<<5)-i。现在的VM可以自动完成这种优化。

四、结论和忠告

确实hashCode有点晦涩,有可能是因为那个数学散列函数。下面是《Effective Java》中的结论点:

1、如果对象有相同的散列码,被映射到同一个散列桶,这样散列表退化称为 链表 ,这样性能降低。

2、相等的对象必须具有相等的散列码

3、为不相等的对象产生不相等的散列码

4、不要试图从散列码计算中排除掉一个对象关键部分来提高性能

Writer:BYSocket(泥沙砖瓦浆木匠)

微博:BYSocket

豆瓣:BYSocket

Posted in Java, 技术

Java 基础:认识&理解关键字 native 实战篇

Writer:BYSocket(泥沙砖瓦浆木匠)

微博:BYSocket

豆瓣:BYSocket

泥瓦匠初次遇见 native是在 java.lang.Object 源码中的一个hashCode方法:

public native int hashCode();

为什么有个native呢?这是我所要学习的地方。所以今天泥瓦匠想要总结下native。

一、认识 native 即 JNI,Java Native Interface

凡是一种语言,都希望是纯。比如解决某一个方案都喜欢就单单这个语言来写即可。Java平台有个用户和本地C代码进行互操作的API,称为Java Native Interface (Java本地接口)。

image

二、用 Java 调用 C 的“Hello,JNI”

我们需要按照下班方便的步骤进行:

1、创建一个Java类,里面包含着一个 native 的方法和加载库的方法 loadLibrary。HelloNative.java 代码如下:

public class HelloNative
{
	static
	{
		System.loadLibrary("HelloNative");
	}
	
	public static native void sayHello();
	
	@SuppressWarnings("static-access")
	public static void main(String[] args)
	{
		new HelloNative().sayHello();
	}
}

首先泥瓦匠让大家注意的是native方法,那个加载库的到后面也起作用。native 关键字告诉编译器(其实是JVM)调用的是该方法在外部定义,这里指的是C。如果大家直接运行这个代码,  JVM会告之:“A Java Exception has occurred.”控制台输出如下:

Exception in thread "main" java.lang.UnsatisfiedLinkError: no HelloNative in java.library.path
	at java.lang.ClassLoader.loadLibrary(Unknown Source)
	at java.lang.Runtime.loadLibrary0(Unknown Source)
	at java.lang.System.loadLibrary(Unknown Source)
	at HelloNative.<clinit>(HelloNative.java:5)

这是程序使用它的时候,虚拟机说不知道如何找到sayHello。下面既可以手动写,自然泥瓦匠是用

    2、运行javah,得到包含该方法的C声明头文件.h

泥瓦匠将HelloNative.java ,简单地 javac javah,如图

image

就得到了下面的 HelloNative.h文件

/* DO NOT EDIT THIS FILE - it is machine generated */
#include <jni.h>
/* Header for class HelloNative */

#ifndef _Included_HelloNative
#define _Included_HelloNative
#ifdef __cplusplus
extern "C" {
#endif
/*
 * Class:     HelloNative
 * Method:    sayHello
 * Signature: ()V
 */
JNIEXPORT void JNICALL Java_HelloNative_sayHello
  (JNIEnv *, jclass);

#ifdef __cplusplus
}
#endif
#endif

jni.h 这个文件,在/%JAVA_HOME%include

3、根据头文件,写C实现本地方法

这里我们简单地实现这个sayHello方法如下:

#include "HelloNative.h"
#include <stdio.h>

JNIEXPORT void JNICALL Java_HelloNative_sayHello
{
	printf("Hello,JNI");	
}

4、生成dll共享库,然后Java程序load库,调用即可。

在Windows上,MinGW GCC 运行如下

gcc -m64  -Wl,--add-stdcall-alias -I"C:\Program Files\Java\jdk1.7.0_71\include" -I"C:\Program Files\Java\jdk1.7.0_71\include\include\win32" -shared -o HelloNative.dll HelloNative.c

-m64表示生成dll库是64位的。然后运行 HelloNative:

    java HelloNative

 

终于成功地可以看到控制台打印如下:

Hello,JNI

三、JNI 调用 C 流程图

 

绘图1

Writer:BYSocket(泥沙砖瓦浆木匠)

微博:BYSocket

豆瓣:BYSocket

Posted in Java, 技术

Java 容器 & 泛型:四、Colletions.sort 和 Arrays.sort 的算法

Writer:BYSocket(泥沙砖瓦浆木匠)

微博:BYSocket

豆瓣:BYSocket

本来准备讲 Map集合 ,还是喜欢学到哪里总结吧。最近面试期准备准备,我是一员,成功被阿里在线笔试秒杀回绝。平常心,继续努力。这次带来 Collections 和 Arrays 类中的经典算法剖析。

 

一、Colletions和Arrays

Collentions 此类完全是服务容器的”包装器“。提供了一些操作或者返回容器的静态方法。而Arrays是用来操作数组的各种方法。其中它们的联系在于其中的Sort方法,也就是这次博客的主题。

 

二、插入,快速、归并基本算法

① 插入排序

{a1},{a2,a3,a4,…,an}}

{{a1⑴,a2⑴},{a3⑴,a4⑴ …,an⑴}}

{{a1(n-1),a2(n-1) ,…},{an(n-1)}}

原理及记忆方法:每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。这通俗的是找座位思想。Java版实现如下

import java.util.Arrays;

public class InsertionSort
{
	public static void main(String[] args)
	{
		int[] intA = new int[]{2,1,3,4,6,7,5};
		System.out.println(Arrays.toString(intA));
		insertionSort(intA);
		System.out.println(Arrays.toString(intA));
	}
	
	public static void insertionSort(int[] a)
	{
		int p,right;
		int temp;
		for (p = 0; p < a.length; p++)
		{
			temp = a[p];
			/**
			 * 将a[p]值往左侧有序列比较,插入。
			 */
			for (right = p; right > 0 && a[right-1] > temp ; right--)
				a[right] = a[right-1];// 置换
			a[right] = temp;
		}
	}
}

右键,run一下可以看到控制台结果:

[2, 1, 3, 4, 6, 7, 5]
[1, 2, 3, 4, 5, 6, 7]

 

② 快速排序

QQ图片20150414181507

快排是基于分治策略的算法,不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。 Java版实现如下:

package javaBasic.algorithm;

import java.util.Arrays;

public class QuickSort
{
	public static void main(String[] args)
	{
		int[] intA = new int[]{2,1,3,4,6,7,5};
		System.out.println(Arrays.toString(intA));
		//middleSort(intA, 0, intA.length - 1);
		//System.out.println(Arrays.toString(intA));
		sort(intA, 0, intA.length - 1);
		System.out.println(Arrays.toString(intA));
	}
	
	// 快速排序中的一个划分过程
	public static int  middleSort(int a[] , int left , int right)
	{
		int temp = a[left];	// 作为中间轴数
		while( left  < right)
		{
			/**
			 * 从右到左,找到第一个比中间轴数小的,移到左端
			 */
			while( left < right && a[right] > temp )
				right--;
			a[left] = a[right];
			
			/**
			 * 从左到右,找到第一个比中间轴数大的,移到右端
			 */
			while( left < right && a[left] < temp)
				left++;
			a[right] = a[left];
		}
		
		/**
		 * 将中间轴数赋值
		 */
		a[left] = temp;
		return left;
	}
	
	// 快速排序
	public static void sort(int[] a , int left, int right)
	{
		if (left < right)
		{
			/**
			 * 根据左右索引相同才停止。
			 * 不同的话,按着分治思想。
			 * 找到中间轴数,一分为二,以此类推。
			 */
			int middle = middleSort(a, left, right);
			sort(a, left, middle - 1);
			sort(a, middle + 1, right);
		}
	}
	
}

记忆方法:分治,就是分工。这里演示的是对分。大量经验数据表面,采用两个枢轴来划分成3份的算法更高效,这就是DualPivotQuicksort。这样也是我们后面讲的JDK源码。右键,run一下可以看到控制台和插入排序一样的结果。

③ 归并排序

c8177f3e6709c93d673b9ed49d3df8dcd000[1]

如图,来自百度百科。归并排序也是一种分治思想的算法,之不用快速是对分。归并是一种分解到合并的算法。如下实现方式:

package javaBasic.algorithm;

import java.util.Arrays;

public class MergeSort
{
	public static void main(String[] args)
	{
		int[] intA = new int[]{10,4,6,3,8,2,5,7};
		System.out.println(Arrays.toString(intA));
		mergeSort(intA,0,intA.length-1);
		System.out.println(Arrays.toString(intA));
	}
	
	public static void mergeSort(int[] a, int left ,int right)
	{
		if (left < right)
		{
			int middle = (left + right) / 2; // 中间索引
			
			mergeSort(a, left, middle);	// 对左侧数组递归
			mergeSort(a, middle+1, right); // 对右侧数组递归
			
			merge(a,left,middle,right); // 归并算法
		}
	}

	private static void merge(int[] a, int left, int middle, int right)
	{
		int [] tmpArr = new int[a.length];
		
		int mid = middle+1;
		int tmpArrLeft = left;// 记录左侧数组的索引
		int tmpLeft = left;
		
		/**
		 * 从两个数组中取出小的一部分复制
		 */
		while (left <= middle && mid <= right) 
		{
			if (a[left] <= a[mid])
				tmpArr[tmpArrLeft++] = a[left++];
			else
				tmpArr[tmpArrLeft++] = a[mid++];
		}
		
		/**
		 * 剩余部分右侧复制
		 */
		while (mid <= right)
		{
			tmpArr[tmpArrLeft++] = a[mid++];
		}
		
		/**
		 * 剩余部分左侧复制
		 */
		while (left <= middle)
		{
			tmpArr[tmpArrLeft++] = a[left++];
		}
		
		/**
		 * 分了再合
		 */
		while(tmpLeft <= right)
		{
			a[tmpLeft] = tmpArr[tmpLeft++];
		}
	}
	
}

结果和上图一样:

[10, 4, 6, 3, 8, 2, 5, 7]
[2, 3, 4, 5, 6, 7, 8, 10]

 

三、JDK数则

在此谢谢@江南白衣大哥的文章,对我帮助很大。以下引用的:

5. JDK7/8中排序算法的改进
面试季的同学背一脑袋的插入、归并、冒泡、快排,那,JDK到底看上了哪家的排序算法?

Colletions.sort(list) 与 Arrays.sort(T[])
Colletions.sort()实际会将list转为数组,然后调用Arrays.sort(),排完了再转回List。
而Arrays.sort(),对原始类型(int[],double[],char[],byte[]),JDK6里用的是快速排序,对于对象类型(Object[]),JDK6则使用归并排序。为什么要用不同的算法呢?

JDK7的进步
到了JDK7,快速排序升级为双基准快排(双基准快排 vs 三路快排);归并排序升级为归并排序的改进版TimSort,一个JDK的自我进化。

JDK8的进步
再到了JDK8, 对大集合增加了Arrays.parallelSort()函数,使用fork-Join框架,充分利用多核,对大的集合进行切分然后再归并排序,而在小的连续片段里,依然使用TimSort与DualPivotQuickSort。

结论
JDK团队的努力,从一些简单的New Features / Change List 根本看不到,所以没事升级一下JDK还是好的

 

我也查看了关于算法追踪到DualPivotQuicksort类,但是这类却不在JDK API。(抛出个问题:为什么这个类不出现在API里面?)哈哈,一看作者是Java之父参与写的,瞬间有研究的激情。根据白衣大哥说的,快速排序由双基准排序到三路快速排序。这也是在大量经验数据表面,采用两个枢轴来划分成3份的算法更高效。算法的思想也是分治思想。

下面又看到了一段发人自省的注释:

/**
    * If the length of an array to be sorted is less than this
    * constant, Quicksort is used in preference to merge sort.
    *  当数组长度小于286,为什么快速排序比归并排序好?
    */
   private static final int QUICKSORT_THRESHOLD = 286;

   /**
    * If the length of an array to be sorted is less than this
    * constant, insertion sort is used in preference to Quicksort.
    * 当数组长度小于47,为什么插入排序比快速排序好?
    */
   private static final int INSERTION_SORT_THRESHOLD = 47;

 

为什么?第二个问题,欢迎大神解答。

我的理解:第一,建立在大量经验数据结果。第二,根据算法时间复杂度和空间复杂度。至于深入了解需要大神解答。

JDK排序顺序图如下:

绘图1

Writer:BYSocket(泥沙砖瓦浆木匠)

微博:BYSocket

豆瓣:BYSocket