文档章节

哈希表和哈希函数和fileinputstream

Oscarfff
 Oscarfff
发布于 2015/05/13 11:02
字数 1789
阅读 79
收藏 4

一、哈希表

       通过记录的存储位置和它的关键字之间建立一个确定的对应关系 f  以及处理冲突的方法,使得每个关键字和结构中一个唯一的存储位置相对应。这样对于关键字 K  根据对应关系 f  ,就可以找到存储在 f(K) .称这种对应关系为 哈希函数,按照这种方法建立的表称为哈希表。

1.1 原 理

       通过记录的存储位置和它的关键字之间建立一个确定的对应关系,使得每个关键字和结构中一个唯一的存储位置相对应。这样对于关键字 K  根据对应关系 f  ,就可以找到存储在 f(K) .称这种对应关系f 为 哈希函数,按照这种方法建立的表称为哈希表。

1.2 冲 突

       对不同的关键字可能得到同一个存储位置-哈希地址,即  key1  不等于 key2 ,但是 f(key1)=f(key2),这种现象称为冲突。

1.3 哈希表的构造方法

1.3.1 均匀哈希函数

       任何一个关键字被映射到地址集合中任何一个地址的概率都是均等的。可以采用直接地址法。`f(K)=a.key+b

二、补充学习知识-fileinputstream

public class FileInputStreamextends InputStream

2.1 FileInputStream 类的主要作用。

FileInputStream obtains input bytes from a file in a file system. What files are available depends on the host environment.

FileInputStream is meant for reading streams of raw bytes such as image data. For reading streams of characters, consider using FileReader.

2.2 read()方法

public int read(byte[] b)
         throws IOException

Reads up to b.length bytes of data from this input stream into an array of bytes. This method blocks until some input is available.

  • Overrides:

  • read in class InputStream

  • Parameters:

  • b - the buffer into which the data is read.

  • Returns:

    the total number of bytes read into the buffer, or -1 if there is no more data because the end of the file has been reached.

  • Throws:

  • IOException - if an I/O error occurs.

  • See Also:

  • InputStream.read(byte[], int, int)

三、实例测试-生成的byte数组要转换成16进制字符串输出

package com.yuan.test;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

import org.apache.log4j.Logger;

public class MD5builder {

	static Logger logger = Logger.getLogger(MD5builder.class);
	// 用来将字节转换成 16 进制表示的字符
	static char hexDigits[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8',
			'9', 'a', 'b', 'c', 'd', 'e', 'f' };

	/**
	 * 对文件全文生成MD5摘要
	 * 
	 * @param file
	 *            要加密的文件
	 * @return MD5摘要码
	 */
	public static String getMD5(File file) {
		FileInputStream fis = null;
		try {
			MessageDigest md = MessageDigest.getInstance("MD5");

			logger.info("MD5摘要长度:" + md.getDigestLength());
			fis = new FileInputStream(file);// 读入文件
			byte[] buffer = new byte[2048];
			int length = -1;
			logger.info("开始生成摘要");
			long s = System.currentTimeMillis();
			while ((length = fis.read(buffer)) != -1) {
				md.update(buffer, 0, length);
				/****
				 * Parameters: input - the array of bytes. offset - the offset
				 * to start from in the array of bytes. len - the number of
				 * bytes to use, starting at offset.
				 * 
				 * 
				 */
			}
			logger.info("摘要生成成功,总用时: " + (System.currentTimeMillis() - s)
					+ "ms");
			byte[] b = md.digest();
			return byteToHexString(b);
			// 16位加密
			// return buf.toString().substring(8, 24);
		} catch (Exception ex) {
			logger.error(ex);
			ex.printStackTrace();
			return null;
		} finally {
			try {
				fis.close();
			} catch (IOException ex) {
				ex.printStackTrace();
			}
		}
	}

	/**
	 * 对一段String生成MD5加密信息
	 * 
	 * @param message
	 *            要加密的String
	 * @return 生成的MD5信息
	 */
	public static String getMD5(String message) {
		try {
			MessageDigest md = MessageDigest.getInstance("MD5");
			logger.info("MD5摘要长度:" + md.getDigestLength());
			byte[] b = md.digest(message.getBytes());
			return byteToHexString(b);
		} catch (NoSuchAlgorithmException e) {
			logger.error(e);
			e.printStackTrace();
			return null;
		}
	}

	/**
	 * 把byte[]数组转换成十六进制字符串表示形式
	 * 
	 * @param tmp
	 *            要转换的byte[]
	 * @return 十六进制字符串表示形式
	 */
	private static String byteToHexString(byte[] tmp) {
		String s;
		// 用字节表示就是 16 个字节
		char str[] = new char[16 * 2]; // 每个字节用 16 进制表示的话,使用两个字符,
		// 所以表示成 16 进制需要 32 个字符
		int k = 0; // 表示转换结果中对应的字符位置
		for (int i = 0; i < 16; i++) { // 从第一个字节开始,对 MD5 的每一个字节
			// 转换成 16 进制字符的转换
			byte byte0 = tmp[i]; // 取第 i 个字节
			str[k++] = hexDigits[byte0 >>> 4 & 0xf]; // 取字节中高 4 位的数字转换,
			// >>> 为逻辑右移,将符号位一起右移
			str[k++] = hexDigits[byte0 & 0xf]; // 取字节中低 4 位的数字转换
		}
		s = new String(str); // 换后的结果转换为字符串
		return s;
	}
}

四、MD5加密算法体会-参考博文

http://blog.csdn.net/magister_feng/article/details/8266540

MD5 (Message Digest  Algorithm 5 信息—摘要算法5 ) 的一些体会

4.1 举例说明

若我们定义一个函数 ,原型为: 

String  MD5 ( Information info)

其中Information 表示任意长度的信息,注意是任意长度的。

实现这个函数的最终要求:

1、对于不同的输入信息,产生的返回值 结果不同 且必须唯一

2、该算法不可逆转,也就是就算拥有 返回结果和算法细节,也不可能推导出输入的初始信息。

下面是MD5算法对一些特定值产生的返回值:

  md5 ("") = d41d8cd98f00b204e9800998ecf8427e 
   md5 ("a") = 0cc175b9c0f1b6a831c399e269772661 
   md5 ("abc") = 900150983cd24fb0d6963f7d28e17f72 
   md5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0 
   md5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b 
      md5("abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz0123456789")

=d174ab98d277d9f5a5611c2c9f419d9f                md5("12345678901234567890123456789012345678901234567890123456789012345678901234567890")  = 57edf4a22be3c955ac49da2e2107b67a 

     对于第二个要求,就是说,给你 一个 32位的字符串d41d8cd98f00b204e9800998ecf8427e,如果不事先告诉你,那你一辈子都别想得出它的输入信息是 一个空白字符。

4.2、一些典型的应用。

   1. 对一段信息(message)产生信息摘要(message-digest),以防止被篡改。比如,在unix下有很多软件在下载的时候都有一个文件名相同,文件扩展名为.md5的文件,在这个文件中通常只有一行文本,大致结构如:

   md5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461 
  这就是tanajiya.tar.gz文件的数字签名。md5将整个文件当作一个大文本信息,通过其不可逆的字符串变换算法,产生了这个唯一的md5信息摘要。如果在以后传播这个文件的过程中,  无论文件的内容发生了任何形式的改变(包括人为修改或者下载过程中线路不稳定引起的传输错误等),只要你对这个文件重新计算md5时就会发现信息摘要不相同,由此可以确定你得到的只是一个不正确的文件。  

    2.防止抵赖。这需要有第三方权威机构的参与。A 写了个文件,权威机构对改文件用MD5算法产生摘要信息做好记录。若以后A说这文件不是我写的,权威机构只需对改文件重新产生摘要信息跟记录在册的摘要信息进行比对,相同的话,就证明是A写的了。这就是所谓的“数字签名”了。

   3. 加密信息。比如在unix系统中用户的密码就是以md5(或其它类似的算法)经加密后存储在文件系统中。当用户登录的时候,系统把用户输入的密码计算成md5值,然后再去和保存在文件系统中的md5值进行比较,进而确定输入的密码是否正确。通过这样的步骤,系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道,而且还在一定程度上增加了密码被破解的难度。


本文转载自:http://blog.csdn.net/magister_feng/article/details/8266523

Oscarfff
粉丝 73
博文 816
码字总数 97116
作品 0
崇明
后端工程师
私信 提问
Common Lisp专题2:hash-table

1)创建哈希表 用make-hash-table函数创建哈希表: CL-USER> (defparameter my-hash (make-hash-table))MY-HASHCL-USER> (setf (gethash 'one-entry my-hash) "one") ;;赋值"one"CL-USER> (......

努力喵
2015/12/27
43
0
数据结构基础(18) --哈希表的设计与实现

哈希表 根据设定的哈希函数 H(key)和所选中的处理冲突的方法,将一组关键字映射到一个有限的、地址连续的地址集 (区间) 上,并以关键字在地址集中的“映像”作为相应记录在表中的存储位置,如...

翡青
2015/01/13
0
0
Redis 源码分析:dict.c 和 dict.h

简介 哈希表是 redis 的核心结构之一,在 redis 的源码中, dict.c 和 dict.h 就定义了 redis 所使用的哈希结构,在这篇文章中,我们将对 dict.c 和 dict.h 进行注解和分析,籍此加深对 redi...

虫虫
2012/03/18
3K
2
密码及加密方式

保护密码的最好方法是使用加盐哈希; 哈希算法 哈希算法是一种单向函数,把任意数量的数据转换成固定长度的“指纹”,这个过程无法逆转。如果输入发生一点改变,由此产生的哈希值完全不同。 ...

春哥大魔王的博客
2018/03/08
57
0
哈希表与应用

一、哈希表 哈希表是一种数据结构,它需要配合哈希函数使用,用于建立索引,便于快速查找。 哈希表的实现一般来说就是一个定长的存储空间,每个位置存储一个对象。如果我们假设定长为N,则可...

不死的达芬奇
2016/12/21
94
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
2.3K
15
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
39
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
40
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
61
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部