大数据开发技能储备&面试指南

ggh:码斯特. 985硕,国内一线大厂工程师,持续分享大数据经验&招聘&面试经验

文章正文

基础知识准备

大数据开发领域 Java 是必备技能,目前业界火热的 Hadoop/Hive/Spark/Flink 等源码实现大部分都是 Java,应用接口层也以 Java 为主。Java 基础知识中 HashMap 几乎是面试必考题,而多线程并发、序列化又是在大数据领域任务调度、网络传输、磁盘 IO 中的核心优化点,因此本章围绕着三个点来阐述。

HashMap 篇

存储结构

在这里插入图片描述

通过上图我们可以清晰的了解到 HashMap 内部哈希表的存储结构,HashMap 是使用链表法来解决哈希冲突的,Java 8 之后,为了提高效率,在 Entry 长度大于 8 之后,会进化成红黑树。我们从最常用的 get/put 方法出发,来了解 HashMap 的核心原理。

1. get 方法

 public V get(Object key) {
     Node<K,V> e;
     return (e = getNode(hash(key), key)) == null ? null : e.value;
 }
final Node<K,V> getNode(int hash, Object key) {
      Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
      if ((tab = table) != null && (n = tab.length) > 0 &&
          (first = tab[(n - 1) & hash]) != null) {
          if (first.hash == hash && // always check first node
              ((k = first.key) == key || (key != null && key.equals(k))))
              return first;
          if ((e = first.next) != null) {
              if (first instanceof TreeNode)
                  return ((TreeNode<K,V>)first).getTreeNode(hash, key);
              do {
                  if (e.hash == hash &&
                      ((k = e.key) == key || (key != null && key.equals(k))))
                      return e;
              } while ((e = e.next) != null);
          }
      }
      return null;
   }
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

get 的过程相对比较简单,主要过程可以分为三步:

  1. 计算 hash 值
  2. 根据 hash 值计算哈希数组的下标
  3. 遍历链表/红黑树,获取最终的 value

我们先来看看 hash 值的计算,如果 key 为 Null,则直接返回头结点。若不为 0,则进入下面的计算:

(h = key.hashCode()) ^ (h >>> 16)

这行比较简单,原理为扰动函数,注意 hashcode 为 32 位的整型,位移加异或的操作是为了把高位的信息叠加到低位,目的是为了降低冲突概率。

接下来我们进入第二步,计算下标:

(table.length-1) & hash

使用哈希表的长度减一和 hash 值做一个与操作。到这里就应该明白,第一步为什么要把高位信息叠加到低位,而不是把低位叠加到高位了。因为 hashcode 是一个 40 亿空间的值,而 HashMap 的初始 size 才 16,大部分场景下 HashMap 的容量是不大的。

第三步比较简单,遍历、取值。

2. put 方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; 
    Node<K,V> p; 
    int n, i;
    if ((tab = table) == null || (n = tab.length) == 0) 
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {                                            
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putT
                        
作者正在撰写中...
隐藏内容 支付可见
内容互动
写评论
加载更多
评论文章
¥9.99 购买
× 订阅 Java 精选频道
¥ 元/月
订阅即可免费阅读所有精选内容