×

hashtable hash

hashtable是什么?什么是hash

admin admin 发表于2022-06-04 14:05:49 浏览114 评论0

抢沙发发表评论

hashtable是什么


Hashtable 类基于 IDictionary 接口,因此该集合中的每一元素是键和值对。

Hashtable 由包含集合元素的存储桶组成。存储桶是 Hashtable 中各元素的虚拟子组,与大多数集合中进行的搜索和检索相比,它可令搜索和检索更简单、更快速。每一存储桶都与一个哈希代码关联,该哈希代码是使用哈希函数生成的并基于该元素的键。

哈希函数是基于键返回数值哈希代码的算法。键是正被存储的对象的某一属性的值。哈希函数必须始终为相同的键返回相同的哈希代码。一个哈希函数能够为两个不同的键生成相同的哈希代码,但从哈希表检索元素时,为每一唯一键生成唯一哈希代码的哈希函数将令性能更佳。

在 Hashtable 中用作元素的每一对象必须能够使用 Object.GetHashCode 方法的实现为其自身生成哈希代码。但是,还可以通过使用 Hashtable 构造函数(该构造函数将 IHashCodeProvider 实现作为其参数之一接受),为 Hashtable 中的所有元素指定一个哈希函数。

在将一个对象添加到 Hashtable 时,它被存储在存储桶中,该存储桶与匹配该对象的哈希代码的哈希代码关联。当在 Hashtable 内搜索一个值时,为该值生成哈希代码,并且搜索与该哈希代码关联的存储桶。

例如,一个字符串的哈希函数可以采用该字符串中每一字符的 ASCII 代码并它们添加到一起来生成一个哈希代码。字符串“picnic”将具有与字符串“basket”的哈希代码不同的哈希代码;因此,字符串“picnic”和“basket”将处于不同的存储桶中。与之相比,“stressed”和“desserts”将具有相同的哈希代码并将处于相同的存储桶中。

using System;
using System.Collections;
public class SamplesHashtable
{

public static void Main()
{

// Creates and initializes a new Hashtable.
Hashtable myHT = new Hashtable();
myHT.Add( “First “, “3 “);
myHT.Add( “Second “, “2 “);
myHT.Add( “Third “, “1 “);

// Displays the properties and values of the Hashtable.
Console.WriteLine( “myHT “ );
Console.WriteLine( “ Count: {0} “, myHT.Count );
Console.WriteLine(myHT[ “First “]);//***也可以这它!
Console.WriteLine( “ Keys and Values: “ );
PrintKeysAndValues( myHT );
}
public static void PrintKeysAndValues( Hashtable myList )
{
IDictionaryEnumerator myEnumerator = myList.GetEnumerator();
Console.WriteLine( “\t-KEY-\t-VALUE- “ );
while ( myEnumerator.MoveNext() )
Console.WriteLine( “\t{0}:\t{1} “, myEnumerator.Key, myEnumerator.Value);

}
}

什么是hash


提到hash,相信大多数同学都不会陌生,之前很火现在也依旧很火的技术区块链背后的底层原理之一就是hash,下面就从hash算法的原理和实际应用等几个角度,对hash算法进行一个讲解。

1、什么是Hash
Hash也称散列、哈希,对应的英文都是Hash。基本原理就是把任意长度的输入,通过Hash算法变成固定长度的输出。这个映射的规则就是对应的Hash算法,而原始数据映射后的二进制串就是哈希值。活动开发中经常使用的MD5和SHA都是历史悠久的Hash算法。

echo md5(“这是一个测试文案“);
// 输出结果:2124968af757ed51e71e6abeac04f98d
在这个例子里,这是一个测试文案是原始值,
2124968af757ed51e71e6abeac04f98d 就是经过hash算法得到的Hash值。整个Hash算法的过程就是把原始任意长度的值空间,映射成固定长度的值空间的过程。

2、Hash的特点
一个优秀的hash算法,需要什么样的要求呢?

a)、从hash值不可以反向推导出原始的数据
这个从上面MD5的例子里可以明确看到,经过映射后的数据和原始数据没有对应关系
b)、输入数据的微小变化会得到完全不同的hash值,相同的数据会得到相同的值
echo md5(“这是一个测试文案“);// 输出结果:2124968af757ed51e71e6abeac04f98decho md5(“这是二个测试文案“);// 输出结果:bcc2a4bb4373076d494b2223aef9f702可以看到我们只改了一个文字,但是整个得到的hash值产生了非常大的变化。
c)、哈希算法的执行效率要高效,长的文本也能快速地计算出哈希值
d)、hash算法的冲突概率要小
由于hash的原理是将输入空间的值映射成hash空间内,而hash值的空间远小于输入的空间。根据抽屉原理,一定会存在不同的输入被映射成相同输出的情况。那么作为一个好的hash算法,就需要这种冲突的概率尽可能小

谁有JAVA面试题分享一下呗,现在复习没有头绪浪费了很多时间


这里有10个经典的Java面试题,也为大家列出了答案。这是Java开发人员面试经常容易遇到的问题,相信你了解和掌握之后一定会有所提高。让我们一起来看看吧。
1.Java的HashMap是如何工作的?
HashMap是一个针对数据结构的键值,每个键都会有相应的值,关键是识别这样的值。
HashMap 基于 hashing 原理,我们通过 put ()和 get ()方法储存和获取对象。当我们将键值对传递给 put ()方法时,它调用键对象的 hashCode ()方法来计算 hashcode,让后找到 bucket 位置来储存值对象。当获取对象时,通过键对象的 equals ()方法找到正确的键值对,然后返回值对象。HashMap 使用 LinkedList 来解决碰撞问题,当发生碰撞了,对象将会储存在 LinkedList 的下一个节点中。 HashMap 在每个 LinkedList 节点中储存键值对对象。
2.什么是快速失败的故障安全迭代器?
快速失败的Java迭代器可能会引发ConcurrentModifcationException在底层集合迭代过程中被修改。故障安全作为发生在实例中的一个副本迭代是不会抛出任何异常的。快速失败的故障安全范例定义了当遭遇故障时系统是如何反应的。例如,用于失败的快速迭代器ArrayList和用于故障安全的迭代器ConcurrentHashMap。
3.Java BlockingQueue是什么?
Java BlockingQueue是一个并发集合util包的一部分。BlockingQueue队列是一种支持操作,它等待元素变得可用时来检索,同样等待空间可用时来存储元素。
4.什么时候使用ConcurrentHashMap?
在问题2中我们看到ConcurrentHashMap被作为故障安全迭代器的一个实例,它允许完整的并发检索和更新。当有大量的并发更新时,ConcurrentHashMap此时可以被使用。这非常类似于Hashtable,但ConcurrentHashMap不锁定整个表来提供并发,所以从这点上ConcurrentHashMap的性能似乎更好一些。所以当有大量更新时ConcurrentHashMap应该被使用。
5.哪一个List实现了最快插入?
LinkedList和ArrayList是另个不同变量列表的实现。ArrayList的优势在于动态的增长数组,非常适合初始时总长度未知的情况下使用。LinkedList的优势在于在中间位置插入和删除操作,速度是最快的。
LinkedList实现了List接口,允许null元素。此外LinkedList提供额外的get,remove,insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。
ArrayList实现了可变大小的数组。它允许所有元素,包括null。 每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增长算法并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
6.Iterator和ListIterator的区别
●ListIterator有add()方法,可以向List中添加对象,而Iterator不能。
●ListIterator和Iterator都有hasNext()和next()方法,可以实现顺序向后遍历,但是ListIterator有hasPrevious()和previous()方法,可以实现逆向(顺序向前)遍历。Iterator就不可以。
●ListIterator可以定位当前的索引位置,nextIndex()和previousIndex()可以实现。Iterator没有此功能。
●都可实现删除对象,但是ListIterator可以实现对象的修改,set()方法可以实现。Iierator仅能遍历,不能修改。
7.什么是CopyOnWriteArrayList,它与ArrayList有何不同?
CopyOnWriteArrayList是ArrayList的一个线程安全的变体,其中所有可变操作(add、set等等)都是通过对底层数组进行一次新的复制来实现的。相比较于ArrayList它的写操作要慢一些,因为它需要实例的快照。
CopyOnWriteArrayList中写操作需要大面积复制数组,所以性能肯定很差,但是读操作因为操作的对象和写操作不是同一个对象,读之间也不需要加锁,读和写之间的同步处理只是在写完后通过一个简单的“=“将引用指向新的数组对象上来,这个几乎不需要时间,这样读操作就很快很安全,适合在多线程里使用,绝对不会发生ConcurrentModificationException ,因此CopyOnWriteArrayList适合使用在读操作远远大于写操作的场景里,比如缓存。
8.迭代器和枚举之间的区别
如果面试官问这个问题,那么他的意图一定是让你区分Iterator不同于Enumeration的两个方面:
●Iterator允许移除从底层集合的元素。
●Iterator的方法名是标准化的。
9.Hashmap如何同步?
当我们需要一个同步的HashMap时,有两种选择:
●使用Collections.synchronizedMap(..)来同步HashMap。
●使用ConcurrentHashMap的
这两个选项之间的首选是使用ConcurrentHashMap,这是因为我们不需要锁定整个对象,以及通过ConcurrentHashMap分区地图来获得锁。
10.IdentityHashMap和HashMap的区别
IdentityHashMap是Map接口的实现。不同于HashMap的,这里采用参考平等。
●在HashMap中如果两个元素是相等的,则key1.equals(key2)
●在IdentityHashMap中如果两个元素是相等的,则key1 == key2
-hashtable