Java面试:BTree、红黑树、哈希算法分析、哈希表源码解析

开课吧IT霈哥2021-02-17 15:31

前言:

打开招聘APP,你会发现很多公司都在招人,机会每天都在发生,想要换工作就要提前做好准备。应广大读者的需要,今天给大家带来新一期的干货啦!高频面试题:BTree、红黑树、哈希算法分析、哈希表源码分析

第一章 BTree、红黑树

1.1 BTree

二叉树binary tree ,是每个结点不超过2的有序树(tree) 。

简单的理解,就是一种类似于我们生活中树的结构,只不过每个结点上都最多只能有两个子结点。

二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点,两边被称作“左子树”和“右子树”。

如图:

红叉树

1.2 红黑树

我们要说的是二叉树的一种比较有意思的叫做红黑树,红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。

如图:

红黑树

红黑树可以通过红色节点和黑色节点尽可能的保证二叉树的平衡,从而来提高效率。

红黑树的约束:

1、节点可以是红色的或者黑色的。

2、根节点是黑色的。

3、叶子节点(特指空节点)是黑色的。

4、每个红色节点的子节点都是黑色的。

5、任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同。

红黑树的特点:

速度特别快,趋近平衡树。

第二章 哈希算法分析、哈希表源码分析

2.1 对象的哈希值

java.lang.Object类中定义了方法:public int hashCode()返回对象的哈希码值,任何类都继承Object,也都会拥有此方法。

定义Person类,不添加任何成员,直接调用Person对象的hashCode()方法,执行Object类的hashCode():

public class Person{}

测试类

public static void main(String[] args){

Person person = new Person();

int code = person.hashCode();

}

红黑树

看到运行结果,就是一个int类型的整数,如果将这个整数转为十六进制就看到所谓的对象地址值,但是他不是地址值,我们将他称为对象的哈希值。

Person类重写hashCode()方法:直接返回0

public int hashCode(){

return 0;

}

运行后,方法将执行Person类的重写方法,结果为0,属于Person类自定义对象的哈希值,而没有使用父类Object类方法hashCode()。

2.2 String对象的哈希值

public static void main(String[] args){

    String s1 = new String("abc");

    String s2 = new String("abc");

    System.out.println(s1.hashCode());

    System.out.println(s2.hashCode());

}

程序分析:两个字符串对象都是采用new关键字创建的,s1==s2的结果为false,但是s1,s2两个对象的哈希值却是相同的,均为96354,原因是String类继承Object,重写了父类方法hashCode()建立自己的哈希值。

String类的hashCode方法源码分析

字符串底层实现是字符数组,被final修饰,一旦创建不能修改。

private final char value[];

定义字符串“abc”或者是new String("abc"),都会转成char value[]数组存储,长度为3。

/*

 *  String类重写方法hashCode()

 *  返回自定义的哈希值

 */

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;

}

String的哈希算法分析

int h = hash,hash是成员变量,默认值0,int h = 0。

判断h==0为true && value.length>0,数组value的长度为3,保存三个字符abc,判断结果整体为true。

char val[] = value,将value数组赋值给val数组。

for循环3次,将value数组进行遍历,取出abc三个字符。

第一次循环: h = 31 * h + val[0],h = 31 * 0 + 97结果:h = 97。

第二次循环: h = 31 * 97 + val[1],h = 31 * 97 + 98结果:h = 3105。

第三次循环: h = 31 * 3105 + val[2],h = 31 * 3105 + 99结果:h =  96354。

return 96354。

算法:31 * 上一次的哈希值+字符的ASCII码值,31属于质数,每次乘以31是为了降低字符串不同,但是计算出相同哈希值的概率。

2.3 哈希表

什么是哈希表呢?

在JDK1.8之前,哈希表底层采用数组+链表实现,即使用数组处理冲突,同一hash值的链表都存储在一个数组里。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。而JDK1.8中,哈希表存储采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。

哈希表的初始化容量,数组长度为16个

当数组容量不够时,扩容为原数组长度的2倍

加载因子为0.75

指示当数组的容量被使用到长度的75%时,进行扩容。

简单的来说,哈希表是由数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的,如下图所示。

红黑树

2.4 哈希表存储字符对象的过程图

红黑树

总而言之,JDK1.8引入红黑树大程度优化了HashMap的性能,那么对于我们来讲保证HashSet集合元素的唯一,其实就是根据对象的hashCode和equals方法来决定的。如果我们往集合中存放自定义的对象,那么保证其唯一,就必须复写hashCode和equals方法建立属于当前对象的比较方式。

2.5 哈希表源代码分析

HashSet集合本身并不提供功能,底层依赖HashMap集合,HashSet构造方法中创建了HashMap对象:

map = new HashMap<>();

因此源代码分析是分析HashMap集合的源代码,HashSet集合中的add方法调研的是HashMap集合中的put方法。

HashMap无参数构造方法的分析

//HashMap中的静态成员变量

static final float DEFAULT_LOAD_FACTOR = 0.75f;

public HashMap() {

    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

}

解析:使用无参数构造方法创建HashMap对象,将加载因子设置为默认的加载因子,loadFactor=0.75F。

HashMap有参数构造方法分析

public HashMap(int initialCapacity, float loadFactor) {

    if (initialCapacity < 0)

    throw new IllegalArgumentException("Illegal initial capacity: " +

    initialCapacity);

    if (initialCapacity > MAXIMUM_CAPACITY)

    initialCapacity = MAXIMUM_CAPACITY;

    if (loadFactor <= 0 || Float.isNaN(loadFactor))

    throw new IllegalArgumentException("Illegal load factor: " +

    loadFactor);

    this.loadFactor = loadFactor;

    this.threshold = tableSizeFor(initialCapacity);

}

解析:带有参数构造方法,传递哈希表的初始化容量和加载因子

如果initialCapacity(初始化容量)小于0,直接抛出异常。

如果initialCapacity大于最大容器,initialCapacity直接等于最大容器

MAXIMUM_CAPACITY = 1 << 30 是最大容量  (1073741824)

如果loadFactor(加载因子)小于等于0,直接抛出异常

tableSizeFor(initialCapacity)方法计算哈希表的初始化容量。

注意:哈希表是进行计算得出的容量,而初始化容量不直接等于我们传递的参数。

tableSizeFor方法分析

static final int tableSizeFor(int cap) {

    int n = cap - 1;

    n |= n >>> 1;

    n |= n >>> 2;

    n |= n >>> 4;

    n |= n >>> 8;

    n |= n >>> 16;

    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

}

解析:该方法对我们传递的初始化容量进行位移运算,位移的结果是 8 4 2 1 码

例如传递2,结果还是2,传递的是4,结果还是4。

例如传递3,结果是4,传递5,结果是8,传递20,结果是32。

Node 内部类分析

哈希表是采用数组+链表的实现方法,HashMap中的内部类Node非常重要

 static class Node<K,V> implements Map.Entry<K,V> {

     final int hash;

     final K key;

     V value;

     Node<K,V> next;

 Node(int hash, K key, V value, Node<K,V> next) {

     this.hash = hash;

     this.key = key;

     this.value = value;

     this.next = next;

}

解析:内部类Node中具有4个成员变量

hash,对象的哈希值

key,作为键的对象

value,作为值得对象(讲解Set集合,不牵扯值得问题)

next,下一个节点对象

存储元素的put方法源码

public V put(K key, V value) {

return putVal(hash(key), key, value, false, true);

}

解析:put方法中调研putVal方法,putVal方法中调用hash方法。

hash(key)方法:传递要存储的元素,获取对象的哈希值

putVal方法,传递对象哈希值和要存储的对象key

putVal方法源码

Node<K,V>[] tab; Node<K,V> p; int n, i;

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

解析:方法中进行Node对象数组的判断,如果数组是null或者长度等于0,那么就会调研resize()方法进行数组的扩容。

resize方法的扩容计算

 if (oldCap > 0) {

     if (oldCap >= MAXIMUM_CAPACITY) {

         threshold = Integer.MAX_VALUE;

         return oldTab;

     }

     else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

              oldCap >= DEFAULT_INITIAL_CAPACITY)

         newThr = oldThr << 1; // double threshold

}

解析计算结果,新的数组容量=原始数组容量<<1,也就是乘以2。

确定元素存储的索引

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null);

解析:i = (数组长度 - 1) & 对象的哈希值,会得到一个索引,然后在此索引下tab[i],创建链表对象。

不同哈希值的对象,也是有可能存储在同一个数组索引下。

遇到重复哈希值的对象

 Node<K,V> e; K k;

 if (p.hash == hash &&

  ((k = p.key) == key || (key != null && key.equals(k))))

e = p;

解析:如果对象的哈希值相同,对象的equals方法返回true,判断为一个对象,进行覆盖操作。

 else {

     for (int binCount = 0; ; ++binCount) {

      if ((e = p.next) == null) {

      p.next = newNode(hash, key, value, null);

      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

      treeifyBin(tab, hash);

      break;

 }

解析:如果对象哈希值相同,但是对象的equals方法返回false,将对此链表进行遍历,当链表没有下一个节点的时候,创建下一个节点存储对象。

以上就是高频面试题:BTree、红黑树、哈希算法分析、哈希表源码分析的全部内容,希望在对您的技术提升有所帮助,更多的面试资料,点击下方图片免费领取

Java

一年之际,在于春。春天如果开了一好头,那么全年都会顺顺利利,很多人想要告别现在所处的状态,那么不妨点击图片,领取一下资料,提升一下自我的技术,为未来不时之需做准备。

上一篇:Java面试难?这份春招必备面试秘籍送给你下一篇:Java面试-例题解析

最新文章

文章图0

Java面试题:面向对象的特征有哪些方面?

抽象:抽象是将一类对象的共同特征总结出来构造类的过程,包括数据抽象和行为抽象两方面。抽象只关注对象有哪些属性和行为,并不关注这些行为的细节是什么。

2021-03-04 16:21:40

文章图1

Java常见面试题:高并发处理包

Hashtable:进行公共数据保存的时候线程的安全性是最高的,因为同一时刻只允许一个线程进行操作;

2021-03-01 15:29:56

文章图2

Java面试中经常被问到的问题有哪些?

当然如果把性别字段设为表的聚集索引,那么就肯定能加快大约一半该字段的查询速度了。聚集索引指的是表本身数据按哪个字段的值来进行排序。因此,聚集索引只能有一个,而且使用聚集索引不会付出额外IO开销。当然你得能舍得把聚集索引这么宝贵资源用到性别字段上。

2021-02-26 17:22:36

文章图3

【开课吧Java免费公开课】大厂高P面试官的面试突击指南

金三银四,突击面试季。对于我们大部分人而言,在进入自己心仪的公司之前少不了准备工作,有一份全面细致对于面试的解析将帮助我们减少许多麻烦。

2021-02-25 15:00:14

文章图4

Java面试题:volatile作用,指令重排相关

多线程主要围绕可见性和原子性两个特性而展开,使用volatile关键字修饰的变量,保证了其在多线程之间的可见性,即每次读取到volatile变量,一定是最新的数据

2021-02-24 17:24:19