看过HashMap源码人应该都知道HashMap是如何根据hash值来计算哈希桶数组下标的，就是通过(n - 1) & hash来计算的，那么为什么用的是位运算而不是取模运算(hash % n)呢？
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
一. 位运算与取模运算时间比较
public class Test {
int a = 1;
int number = 100000; // 数据集数量，初始定义为十万
// 位运算
public long bitwise() {
long start = System.currentTimeMillis();
//从十万开始，一直到Integer的最大值，计算所需时间
for (int i = number; i > 0; i++) {
a &= i;
}
long end = System.currentTimeMillis();
long time = end - start;
System.out.println("位运算时间为：" + time + "ms");
return time;
}
// 取模运算
public long module() {
long start = System.currentTimeMillis();
for (int i = number; i > 0; i++) {
a %= i;
}
long end = System.currentTimeMillis();
long time = end - start;
System.out.println("取模运算时间为：" + time + "ms");
return time;
}
public static void main(String[] args) {
Test t = new Test();
t.bitwise();
t.module();
}
}
测试结果：
从测试结果我们可以看出，如果数据集足够的大，那么取模运算的时间将会是位运算时间的十几倍(每个人的测试结果都可能不一样，但位运算的时间远远小于取模运算)。这只是一方面，如果数量集足够大的话，那么HashMap的初始容量肯定不够，这也就触发了HashMap的扩容机制。在jdk1.7中，HashMap需要重新生成链表，重新计算hash值，这就更大大的增加了运行时间，将会从十几倍有可能变成几十倍或者上百倍。从运行时间上上来看，位运算效率要远远高于取模运算。(ps:jdk1.8对resize()进行了优化，在此不说，因为我还不懂，想了解的可以自行百度)。
二.位运算是如何保证索引不越界
讲到这，我们也就要想想为什么HashMap的容量是2的n次幂？两者之间有着千丝万缕的联系。
当 n 是2的次幂时， n - 1 通过 二进制表示即尾端一直都是以连续1的形式表示的。当(n - 1) 与 hash 做与运算时，会保留hash中 后 x 位的 1，这样就保证了索引值 不会超出数组长度。
同时当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n。
hmi_java
发布了7 篇原创文章 · 获赞 4 · 访问量 167
私信
关注
标签：取模,hash,HashMap,System,long,哈希,Java,运算
来源： https://blog.csdn.net/hm_135/article/details/104630230

看过HashMap源码人应该都知道HashMap是如何根据hash值来计算哈希桶数组下标的，就是通过(n - 1) & hash来计算的，那么为什么用的是位运算而不是取模运算(hash % n)呢？

HashMap源码的简单解析

 if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

一. 位运算与取模运算时间比较

public class Test {
	int a = 1;
	int number = 100000; // 数据集数量，初始定义为十万

	// 位运算
	public long bitwise() {
		long start = System.currentTimeMillis();

        //从十万开始，一直到Integer的最大值，计算所需时间
		for (int i = number; i > 0; i++) {  
			a &= i;
		}
		long end = System.currentTimeMillis();
		long time = end - start;
		System.out.println("位运算时间为：" + time + "ms");
		return time;
	}

	// 取模运算
	public long module() {
		long start = System.currentTimeMillis();
		for (int i = number; i > 0; i++) {
			a %= i;
		}
		long end = System.currentTimeMillis();
		long time = end - start;
		System.out.println("取模运算时间为：" + time + "ms");
		return time;
	}

	public static void main(String[] args) {
		Test t = new Test();
		t.bitwise();
		t.module();
	}
}


测试结果： 



从测试结果我们可以看出，如果数据集足够的大，那么取模运算的时间将会是位运算时间的十几倍（每个人的测试结果都可能不一样，但位运算的时间远远小于取模运算）。这只是一方面，如果数量集足够大的话，那么HashMap的初始容量肯定不够，这也就触发了HashMap的扩容机制。在jdk1.7中，HashMap需要重新生成链表，重新计算hash值，这就更大大的增加了运行时间，将会从十几倍有可能变成几十倍或者上百倍。从运行时间上上来看，位运算效率要远远高于取模运算。(ps:jdk1.8对resize()进行了优化，在此不说，因为我还不懂，想了解的可以自行百度)。

二.位运算是如何保证索引不越界

讲到这，我们也就要想想为什么HashMap的容量是2的n次幂？两者之间有着千丝万缕的联系。

当 n 是2的次幂时， n - 1 通过 二进制表示即尾端一直都是以连续1的形式表示的。当(n - 1) 与 hash 做与运算时，会保留hash中 后 x 位的 1，这样就保证了索引值 不会超出数组长度。

同时当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n。

 

数组的遍历  获取最大值最小值 数组的反转 数组的查找 练习 定义方法创建指定大小的数组，并添加指定元素 拼接两个数组

感觉数组的运用还是得靠大量的实操练习才能深刻理解，像遍历取大小值和反转查下标这种系统本身就有提供现成的方法，但不通过方法就能实现功能的练习还是很必要的，这些会加强你对数组的理解。下面就罗列了些常用的方法和一些数组的练习

数组的遍历
根据数组中的索引值的改变，一个一个的访问数组中的元素，再把每个元素都打印出来
package Chating;
public class Shuzu {
	public static void main(String[] args) {
		//数组的遍历
		int[] arr = {1,2,3,4,5};
		for(int i = 0; i < arr.length; i++) {//数组的长度  arr.length
			System.out.print(arr[i]+" ");//把元素都打印出来,每个中间加空格
		}
	}
}


数组获取最大值
给定一个数组，求出数组的最大值
思路：擂台思想
预设一个默认最大值max当做擂主，数组中所有元素为挑战者，通过遍历与max一一挑战比较大小，如果数组中元素比max大，就把该元素的值赋值给max，否则不做任何操作，进行下一组的比较，循环结束max存储的就是最大值


package Chating;
public class Shuzu {
   public static void main(String[] args) {
   	int[] arr = {11,257,0,99};
   	int max = 0;//预设最大值max
   	for(int i = 0; i < arr.length; i++) {//遍历数组 一个一个与max比较大小
   		if (max<arr[i]) {//如果max比数组元素小
   			max = arr[i];//数组元素赋值给max
   		}
   	}
   	System.out.println("最大值为"+max);//循环结束max储存的就是最大值
   }
}


获取最小值
与获取最大值同理，把预设的最大值max变成最小值min，再通过遍历与数组元素进行比较，如果数组元素比min小，就赋值给min，否则不做任何操作，进行下一组的比较，循环结束min即为最小值
package Chating;
public class Shuzu {
	public static void main(String[] args) {
		int[] arr = {11,257,0,99};
		int min = 0;//预设最小值min
		for(int i = 0; i < arr.length; i++) {//遍历数组 一个一个与min比较大小
			if (min>arr[i]) {//如果min比数组元素大
				min = arr[i];//数组元素赋值给min
			}
		}
		System.out.println("最小值为"+min);//循环结束min储存的就是最小值
	}
}


数组的反转
元素前后的交换 如{1,2,3,4} — {4,3,2,1}
思路：


预设个数值t做中间交换值


把首位值（arr[0]）赋值给t做储存


再把末位值（arr[arr.lenght]）赋值给首位值


最后把储存在t中的首位值赋值给末位值（arr[arr.lenght]）


完成前后位数组的交换，通过遍历完成整个数组的交换
注意：前一位的遍历坐标必须小于后位的坐标，否则如果数组中的元素数量是偶数，前位坐标大于后位坐标，就会重新交换回原样




package Chating;

public class Shuzu {
	public static void main(String[] args) {
		int[] arr = {11,257,0,99};
		for (int i = 0,j = arr.length-1; i<j;i++,j--) {//i为第一位的坐标，j为末位坐标，根据循环递增减
            //前一位的遍历坐标必须小于后位的坐标 i<j
			int t = arr[i];//预设中间数t被赋值保存第一位的数值
			arr[i] = arr[j];//把末位的数值赋值给第一位
			arr[j] = t;//把t中保存的第一位的数值赋值给末位
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
	}
}


数组的查找
指定元素数值，从数组中找出坐标
package Chating;

import java.util.Scanner;
public class Shuzu {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("请输入要查询的元素:");
		int num = sc.nextInt();
		int index = 0;//定义一个变量，用于接收索引值
		int[] arr = {34,0,6,208};
		for(int i = 0; i < arr.length; i++) {
			if(num == arr[i]) {//判断输入的数值是否与数组中的元素相同
				index = i;//如果有相同的数值就输出坐标
				System.out.println("数组中该元素的索引为： " + i);
				break;
			}
			if (i==arr.length-1) {//表示遍历完数组全部长度没有找出相同数值
				System.out.println("查无此元素");
			}
		}
	}
}





练习
定义个方法，创建一个指定大小的数组，并向该数组添加指定元素，最后打印
package Chating;

import java.util.Scanner;
public class Shuzu {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("请输入数组大小:");
		int num = sc.nextInt();//键盘录入指定数组大小
		shuzu(num);//调用方法
	}
	public static void shuzu(int num) {
		int j = 0;
		int[] arr = new int[num];
		while (j<num) {//循环输入元素的次数等于指定数组的大小数
			Scanner sc = new Scanner(System.in);
			System.out.print("请输入要加入的元素:");
			int n = sc.nextInt();//键盘录入要加入的元素
			arr[j]+=n;//每个元素下标上循环赋值
			j++;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
	}
}



给出两个数组，数组A {1,3,5,7,9,11}数组B{2，4,6,8,10}拼接为数组C{1,3,5,7,9,11,2,4,6,8,10}；
package Chating;

public class Shuzu {
	public static void main(String[] args) {
			int[] A = {1,3,5,7,9,11};
			int[] B = {2,4,6,8,10};
			int[] C = new int[A.length + B.length];//创建一个C元素个数是A和B的和
			for(int i = 0; i < A.length; i++) {//把数组A中的元素赋值到C中，
				C[i] = A[i];//赋值的个数为A.length个
			}
			for(int i = 0; i < B.length; i++) {//把数组B中的元素赋值到C中，
				C[A.length + i] = B[i];//赋值的个数为A.length个，赋值的起点为前一循环A.length + i开始
			}//C中原有A种的6个元素，所以B数组的赋值从下标6开始，往后递增（A.length + i = 6）
			for(int i = 0; i < C.length; i++) {
				System.out.print(C[i]+" ");
			}
	}
}

    
第7章  数组
数组是一种复合型的数据类型，它具有相同类型的数据集合。数组中的每一个数据称为数组的元素，数组元素是有序的。在本章中，主要介绍数组的知识，其中包括数组的定义、创建数组、数组的使用以及多维数组。
7.1  数组基础 
数组是一种线性表，是一组数据的集合。用户可以比较方便的获取到这个线性表中的任何一个元素，并且可以对其中的元素值进行修改。数组中的元素会根据下标的顺序在内存中按照顺序来进行存放。本节中就主要介绍数组的基础知识。
7.1.1  数组概述
数组就是一组数的集合，集合中的数据必须是相同类型的。并且每一个数组都有一个名字，也就是数组名，用户可以通过数组名来访问数组中的元素。
7.1.2  创建数组
在Java中，一切的事物都是对象，数组也不例外，但是把数组看做是一个同种类型变量的集合会更加合适一些。在这样一个集合中，所有的数据都有相同的数据类型，而且使用统一的名称，可以通过下标来对其中的各个元素进行区分。数组在使用以前必须要进行声明，然后要对声明的数组进行初始化，最后才可以在数组中进行元素的存取。
7.1.3  初始化数组
前面已经对数组进行了声明创建，这样就可以对数组中的元素进行访问了。而且在数组中的所有的元素都会设置成为默认的值。如下示例就是打印出各个不同类型数组创建后的默认值。
7.2  数组的使用
在前面介绍了对数组的声明、创建和初始化。本节中，就主要介绍一下数组的使用，其中包括有对数组的复制、获取到数组的长度等。
7.2.1  获取数组长度
数组作为一个Java内部定义的对象，具有一个length属性，当该数组被初始化完成之后，就会将数组的长度复制给length属性。例如创建一个数组，它的长度为10。则length的值为10。
int [] array1=new int [10];
int i= array1.length;
7.2.2  数组拷贝
数组的复制可以直接将一个数组变量拷贝给另一个，这时候数组都会指向同一个数组，如果有两个数组array1和array2，可以执行下面语句。
array1=array2;
7.2.1  带参数运行
在Window系统的命令提示符窗口进行程序的编译和运行时，可以带入一些参数，以供程序在运行时使用。这一点不同于Scanner类的输入语句。实现带参数运行的效果，是因为在main方法中都带有一个字符串类型的数组，这个数组就是参数。例如以下程序，在命令提示符窗口中进行编译和运行。
7.3  多维数组
所谓的多维数组是指数组的嵌套，也就是一个数组中的元素也是数组。是数组的另一种表现形式。数组的维数是根据所嵌套的层数来决定。如果一个数组的每一个元素是一个数组，就成为二维数组。如果第二位数组的每一个元素也是一个数组，则成为三维数组。
7.3.1  多维数组基础
前面介绍的数组元素是由索引来进行访问的，那么在多维数组中，就需要使用多个索引来对数组元素进行访问。
7.3.2  实现多维数组
实际上在Java中只存在有一位数组，而多维数组的实现只不过是数组中的数组，例如一个二维数组，一个数组类型的变量指向一个一维数组，而这个一维数组中有有n个元素。这样就组成了一个二维数组。
7.3.3  创建不规则数组
前面介绍过，在Java中的多维数组实际上是数组中的数组。如果这些数组的大小不同，就是不规则数组，例如以下语法是声明一个不规则数组。
int [][]n=new int[4][];
通过以上的代码可以看出，在数组的声明时，值确定了数组的行数，而没有对数组的列做任何的规定。
7.4  数组排序
数组中存放的都是一些数据，有时候就需要对其中的数据按照一定的规则进行排列，例如学生成绩管理，就需要将学生的成绩或者是编号按照大小顺序进行排列。这时就需要使用到数组的排列算法。对数组的排列主要分为三种，分别是选择排列法、冒泡法、快速排序。本节就主要介绍一下这三种不同的数组排列方法。
7.4.1  选择排序
选择排序是最简单的额一种数组排序方法。使用选择排序法，首先要将数组中的一个最大数选出来，然后将最大的数和数组中的第一个元素进行交换，然后在次进行遍历，从剩余的元素中再选出一个最大的，和第二个数进行交换。依次类推，如果该数组中有n个元素，则在进行n此遍历后，数组就会以降序排列。
7.4.2  冒泡排序
冒泡排序法也是一种交换排序算法，可以将数组中的元素看做是水中的物体，密度比较大的就是数值比较大的元素，密度比较小的就是数值比较小的元素。对数组中元素的排序就是物体上浮的过程。首先让第一个元素和数组中的每一个元素进行比较，根据比较的结果进行位置的调换，这样较小的元素自然就会排到上面，大的元素就会降到下面。
7.4.3  快速排序
    快速排序法是对冒泡排序法的一种改进，大大提高了排序的效率。它首先通过一趟排序将要排序的数据分割成两个独立的部分，首先设置一个中间数据，然后将比该数据小的放置到左边，而比它大的数据则放置到右边。
7.5  小结
在本节中主要介绍了数组的内容。先后介绍了数组的创建和使用、数组拷贝、数组排序、以及多维数组的使用。结束完本章的学习，Java的基础知识已经基本完成，从下一章开始将会开始学习Java的面向对象性特性。面向对象性是Java的主要特性，也是区别于别的语言的地方，希望大家认真学习后边的内容。

转载于:https://www.cnblogs.com/yoogoo/archive/2012/04/23/2467263.html