面试题随笔-21/4/14

今日面经2

链接：https://www.nowcoder.com/discuss/639062?type=post&order=time&pos=&page=1&channel=-1&source_id=search_post_nctrack

hashmap中hash的计算

链接：https://www.cnblogs.com/mxxct/p/13857097.html

hash 计算

JDK1.8
HashMap源码

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

右移16位相当于将高16位移入到低16位，再与原hashcode做异或计算（位相同为0，不同为1）可以将高低位二进制特征混合起来 => 高16位没有发生变化，但是低16位改变了

拿到的hash值会参与hashmap中数组槽位的计算，计算公式：(n - 1) & hash。

高区的16位很有可能会被数组槽位数的二进制码锁屏蔽，如果我们不做刚才移位异或运算，那么在计算槽位时将丢失高区特征

虽然丢失了高区特征，不同hashcode也可以计算出不同的槽位来，但是如果两个hashcode很接近时，高区的特征差异可能会导致一次哈希碰撞。

使用异或运算的原因

异或运算能更好的保留各部分的特征，如果采用 & 运算计算出来的值会向0靠拢，采用 | 运算计算出来的值会向1靠拢

为什么槽位数必须使用2^n / 为什么要 &length-1

为了让哈希后的结果更加均匀，减少hash碰撞

扩容后Hash值计算

length * 2，即新增的bit位是1，在 (n - 1) & hash 时，只需要判断新增加的这一个bit位，如果是0的话，说明索引不变，如果变成1了，索引变成原索引+扩容前的容量大小

gc对象生命周期

在 Java 中，堆被划分成两个不同的区域：新生代 ( Young )、老年代 ( Old )。新生代 ( Young ) 又被划分为

三个区域：Eden、From Survivor、To Survivor。

这样划分的目的是为了使 JVM 能够更好的管理堆内存中的对象，包括内存的分配以及回收。

老年代：

老年代主要存放在程序中生命周期长的对象。老年代因为其中对象比较稳定，所以Major GC不会频繁的执行。在进行Major GC之前通常都会先执行一次Minor GC,Minor GC执行完后可能会有新生代的对象晋升到老年代之中，然后导致老年代的空间不足才触发Major GC。

永久代：java7之前

永久存储区是一个常驻内存区域，用于存放JDK自身所携带的Class,Interface的元数据，也就是说它存储的是运行环境必须的类信息，被装载进此区域的数据是不会被垃圾回收器回收掉的，关闭JVM才会释放此区域所占用的内存。

java8以后是元空间。

元空间的本质和永久代类似，都是对JVM规范中方法区的实现。不过元空间与永久代之间最大的区别在于：元空间并不在虚拟机中，而是使用本地内存。因此，默认情况下，元空间的大小仅受本地内存限制，但可以通过以下参数来指定元空间的大小。

gc判断对象存活的方法

引用计数

优点：实现简单
缺点：难以解决对象循环引用的问题

可达性分析

通过一系列的称为“GC Roots”的对象作为起始点，从这些节点考试向下探索，搜索所走过的路径称为“引用链”，当一个对象到GC Roots没有任何引用链相连（用图论的话来说，就是从GC Roots到这个对象不可达）时，则证明此对象是不可用的。

gc root包括哪些？

虚拟机栈（栈帧中的本地变量表）中引用的对象；
方法区中类静态属性引用的对象；
方法区中常量引用的对象；
本地方法栈中JNI（即一般说的Native方法）引用的对象。

给你5张牌，其中包含两张大小王，判断是否是顺子

class Solution {
    public boolean isStraight(int[] nums) {
        Set<Integer> repeat = new HashSet<>();
        int max = 0, min = 14;
        for(int num : nums) {
            if(num == 0) continue; // 跳过大小王
            max = Math.max(max, num); // 最大牌
            min = Math.min(min, num); // 最小牌
            if(repeat.contains(num)) return false; // 若有重复，提前返回 false
            repeat.add(num); // 添加此牌至 Set
        }
        return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

链表反转

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

二叉树的遍历

前中后序递归遍历

/**
     * 前序遍历
     * 递归
     */
public void preOrder(BinaryNode<AnyType> Node)
{
  if (Node != null)
  {
    System.out.print(Node.element + " ");
    preOrder(Node.left);
    preOrder(Node.right);
  }
}

/**
     * 中序遍历
     * 递归
     */
public void midOrder(BinaryNode<AnyType> Node)
{
  if (Node != null)
  {
    midOrder(Node.left);
    System.out.print(Node.element + " ");
    midOrder(Node.right);
  }
}

/**
     * 后序遍历
     * 递归
     */
public void posOrder(BinaryNode<AnyType> Node)
{
  if (Node != null)
  {
    posOrder(Node.left);
    posOrder(Node.right);
    System.out.print(Node.element + " ");
  }
}

层序遍历

/*
     * 层序遍历
     * 递归
     */
public void levelOrder(BinaryNode<AnyType> Node) {
  if (Node == null) {
    return;
  }

  int depth = depth(Node);

  for (int i = 1; i <= depth; i++) {
    levelOrder(Node, i);
  }
}

private void levelOrder(BinaryNode<AnyType> Node, int level) {
  if (Node == null || level < 1) {
    return;
  }

  if (level == 1) {
    System.out.print(Node.element + "  ");
    return;
  }

  // 左子树
  levelOrder(Node.left, level - 1);

  // 右子树
  levelOrder(Node.right, level - 1);
}

public int depth(BinaryNode<AnyType> Node) {
  if (Node == null) {
    return 0;
  }

  int l = depth(Node.left);
  int r = depth(Node.right);
  if (l > r) {
    return l + 1;
  } else {
    return r + 1;
  }
}

/*
     * 层序遍历
     * 非递归
     */
public void levelOrder1(BinaryNode<AnyType> Node) {
  if (Node == null) {
    return;
  }

  BinaryNode<AnyType> binaryNode;
  Queue<BinaryNode> queue = new LinkedList<>();
  queue.add(Node);

  while (queue.size() != 0) {
    binaryNode = queue.poll();

    System.out.print(binaryNode.element + "  ");

    if (binaryNode.left != null) {
      queue.offer(binaryNode.left);
    }
    if (binaryNode.right != null) {
      queue.offer(binaryNode.right);
    }
  }
}

前中后序非递归遍历

/**
     * 前序遍历
     * 非递归
     */
public void preOrder1(BinaryNode<AnyType> Node)
{
  Stack<BinaryNode> stack = new Stack<>();
  while(Node != null || !stack.empty())
  {
    while(Node != null)
    {
      System.out.print(Node.element + "   ");
      stack.push(Node);
      Node = Node.left;
    }
    if(!stack.empty())
    {
      Node = stack.pop();
      Node = Node.right;
    }
  }
}

/**
     * 中序遍历
     * 非递归
     */
public void midOrder1(BinaryNode<AnyType> Node)
{
  Stack<BinaryNode> stack = new Stack<>();
  while(Node != null || !stack.empty())
  {
    while (Node != null)
    {
      stack.push(Node);
      Node = Node.left;
    }
    if(!stack.empty())
    {
      Node = stack.pop();
      System.out.print(Node.element + "   ");
      Node = Node.right;
    }
  }
}

/**
     * 后序遍历
     * 非递归
     */
public void posOrder1(BinaryNode<AnyType> Node)
{
  Stack<BinaryNode> stack1 = new Stack<>();
  Stack<Integer> stack2 = new Stack<>();
  int i = 1;
  while(Node != null || !stack1.empty())
  {
    while (Node != null)
    {
      stack1.push(Node);
      stack2.push(0);
      Node = Node.left;
    }

    while(!stack1.empty() && stack2.peek() == i)
    {
      stack2.pop();
      System.out.print(stack1.pop().element + "   ");
    }

    if(!stack1.empty())
    {
      stack2.pop();
      stack2.push(1);
      Node = stack1.peek();
      Node = Node.right;
    }
  }
}