<mark>哈希</mark>

<mark>请谈一谈，hashCode() 和equals() 方法的重要性体现在什么地方？</mark>

Java中的HashMap使用hashCode()和equals()方法来确定键值对的索引，当根据键获取值的时候也会用到这两个方法。如果没有正确的实现这两个方法，两个不同的键可能会有相同的hash值，因此，可能会被集合认为是相等的。而且，这两个方法也用来发现重复元素。所以这两个方法的实现对HashMap的精确性和正确性是至关重要的。

<mark>请说一说，Java中的HashMap的工作原理是什么？</mark>

HashMap类有一个叫做Entry的内部类。这个Entry类包含了key-value作为实例变量。 每当往hashmap里面存放key-value对的时候，都会为它们实例化一个Entry对象，这个Entry对象就会存储在前面提到的Entry数组table中。Entry具体存在table的那个位置是 根据key的hashcode()方法计算出来的hash值（来决定）。

<mark>介绍一下，什么是hashmap?</mark>

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。
HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。

HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。容量 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。

hashmap共有4个构造函数：

// 默认构造函数。HashMap()

// 指定“容量大小”的构造函数

HashMap(int capacity)

// 指定“容量大小”和“加载因子”的构造函数

HashMap(int capacity, float loadFactor)

// 包含“子Map”的构造函数

HashMap(Map<? extends K, ? extends V> map)

<mark>讲一讲，如何构造一致性 哈希算法。</mark>

先构造一个长度为232的整数环（这个环被称为一致性Hash环），根据节点名称的Hash值（其分布为[0, 232-1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到其Hash值（其分布也为[0, 232-1]），接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。

这种算法解决了普通余数Hash算法伸缩性差的问题，可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。

== 请问，Object作为HashMap的key的话，对Object有什么要求吗？==

要求Object中hashcode不能变。

<mark>请问 hashset 存的数是有序的吗？</mark>

Hashset是无序的。

<mark>树</mark>

<mark>TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？</mark>

TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。Collections工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。
代码示例：

public class
Student implements Comparable<Student> {
     private String
name;        // 姓名
     private int
age;            // 年龄
     public Student(String name, int age) {
         this.name = name;
         this.age = age;
     }
     @Override
     public String toString() {
         return "Student [name=" +
name + ", age=" + age + "]";
     }
     @Override
     public int compareTo(Student o) {
         return this.age - o.age; // 比较年龄(年龄的升序)
     }
 }
 import java.util.Set;
 import java.util.TreeSet;
 class Test01 {
     public static void main(String[] args) {
         Set<Student> set = new
TreeSet<>();     // Java 7
     }
 }
 import java.util.Set;
 import java.util.TreeSet;
 class Test01 {
     public static void main(String[] args) {
         Set<Student> set = new
TreeSet<>();     // Java 7的钻石语法(构造器后面的尖括号中不需要写类型)
         set.add(new Student("Hao
LUO", 33));
         set.add(new Student("XJ
WANG", 32));
         set.add(new Student("Bruce
LEE", 60));
         set.add(new Student("Bob
YANG", 22));
  
         for(Student stu : set) {
             
System.out.println(stu);
         }
 // 
         set.add(new Student("Hao
LUO", 33));
         set.add(new Student("XJ
WANG", 32));
         set.add(new Student("Bruce
LEE", 60));
         set.add(new Student("Bob
YANG", 22));
         for(Student stu : set) {
             
System.out.println(stu);
         }
 // 输出结果: 
 // Student [name=Bob YANG, age=22]
 // Student [name=XJ WANG, age=32]
 // Student [name=Hao LUO, age=33]
 // Student [name=Bruce LEE, age=60]
     }
 }
 // Student [name=Bob YANG, age=22]
 // Student [name=XJ WANG, age=32]
 // Student [name=Hao LUO, age=33]
 // Student [name=Bruce LEE, age=60]
     }
 }

<mark>如何打印二叉树每层的节点？</mark>

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	// 定义节点
	class Node {
		int val;
		Node left;
		Node right;

		public Node(int val) {
			this.val = val;
		}
	}

	public ArrayList<Integer> gzy; // 保存根左右的序列
	public ArrayList<Integer> zgy; // 保存左跟右的序列
	public ArrayList<Node> pack; // 保存已经排好的节点

	public static void main(String[] args) {
		Main main = new Main();
		main.getResult();

	}

	public void getResult() {
        //init
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        gzy = new ArrayList<>();
        zgy = new ArrayList<>();
        for(int i = 0; i < count; i++) {
            gzy.add(scanner.nextInt());
        }
        for(int j = 0; j < count; j++) {
            zgy.add(scanner.nextInt());
        }
        pack = new ArrayList<>();       // 已经还原的节点
        
        //exception
        if(count== 1) {
            System.out.println(gzy.get(0));
            return;
        }
        // 构造最左侧节点的二叉树
        Node node = new Node(gzy.get(0));
        pack.add(node);
        int index1 = 1;     // 根左右的下标
        Node tmp = node;
        while(gzy.get(index1)!= zgy.get(0)) {      // 如果没访问到最左边的叶子节点,继续还原最左侧二叉树
            tmp.left = new Node(gzy.get(index1++));
            tmp = tmp.left;
            pack.add(tmp);
        }
        tmp.left = new Node(gzy.get(index1++));
        pack.add(tmp.left);
        
        // 加入剩余的节点完善二叉树
        for(int k = index1; k < gzy.size(); k++) {
            fillErCS(gzy.get(k));
        }
        
        // 层次遍历
        ArrayList<Node> res = new ArrayList<>();
        res.add(node);
        int num = 0;
        while(res.size()!= num) {
            System.out.print(res.get(num).val + "");
            if(res.get(num).left != null) {
                res.add(res.get(num).left);
            }
            if(res.get(num).right != null) {
                res.add(res.get(num).right);
            }
            num++;
        }
    }

	// 将值为val的节点加入二叉树
	private void fillErCS(int val) {
		int index = zgy.indexOf(val);
		// 每一个遍历的节点都是val节点的根或者在其左边
		for (int i = index - 1; i >= 0; i--) {
			if (findNode(zgy.get(i)) != null) { // 找到待插入节点的根节点或者其左边的节点
				Node node = findNode(zgy.get(i));
				insert(node, val);
				break;
			}
		}
	}

	// 将节点val插入二叉树
	private void insert(Node node, int val) {
        if(zgy.indexOf(node.val)> zgy.indexOf(val)) {  // node在待插入节点的右边
            if(node.left == null) {
                node.left= new Node(val);
                pack.add(node.left);
                return;
            }
            insert(node.left, val);
        }else{     //node在待插入节点的左边或是其根
            if(node.right == null) {
                node.right= new Node(val);
                pack.add(node.right);
                return;
            }
            insert(node.right, val);
        }
    }

	// 根据val找到pack里的节点
	private Node findNode(int val) {
		for (Node node : pack) {
			if (node.val == val) {
				return node;
			}
		}
		return null;
	}
}

<mark>从上往下打印出二叉树的每个节点，同层节点从左至右打印</mark>

import java.util.ArrayList;

import javax.swing.tree.TreeNode;
/** * 从上往下打印二叉树每个节点，同层节点从左至右打印 * @author 96971 * */
public class TreeNode {
	int val=0;
	TreeNode left=null;
	TreeNode right=null;
	public TreeNode(int val) {
		this.val=val;
	}
	
	
}
 class Solution{
	public ArrayList<Integer> printFromTopToBootom(TreeNode root){
		ArrayList<Integer> vlist=new ArrayList<>();//存储二叉树节点的值
		ArrayList<TreeNode> treeNodes=new ArrayList<>();//存储二叉树的节点
		if (root==null) {
			return vlist;
		}
		treeNodes.add(root);
		vlist.add(root.val);
		for (int i = 0; i < treeNodes.size(); i++) {
			TreeNode node=treeNodes.get(i);
			if (node.left!=null) {
				treeNodes.add(node.left);
				vlist.add(node.left.val);
			}
			if (node.right!=null) {
				treeNodes.add(node.right);
				vlist.add(node.right.val);
			}
		}
		
		return vlist;
	}
}

<mark>如何知道二叉树的深度？</mark>

实现二叉树的深度方式有两种，递归以及非递归。

①递归实现：

为了求树的深度，可以先求其左子树的深度和右子树的深度，可以用递归实现，递归的出口就是节点为空。返回值为0；
示例代码：

//递归方式一：
public int findDeep(BiTree root){
	int deep=0;
	if(root!=null){
		int lChildDeep=findDeep(root.left);
		int rChildDeep=findDeep(root.right);
		deep=lChildDeep>rChildDeep? lChildDeep+1:rChildDeep+1;
	}
	
	return deep;
}
//递归方式二：
public int findDeep1(BiTree root){
	if(root==null){
	return 0;
	}
	else{
		int lChildDeep=findDeep(root.left);
		int rChildDeep=findDeep(root.right);
		return lChildDeep>rChildDeep? lChildDeep+1:rChildDeep+1;
	}
}

②非递归实现：

利用层次遍历的算法，设置变量level记录当前节点所在的层数，设置变量last指向当前层的最后一个节点，当处理完当前层的最后一个节点，让level指向+1操作。设置变量cur记录当前层已经访问的节点的个数，当cur等于last时，表示该层访问结束。

层次遍历在求树的宽度、输出某一层节点，某一层节点个数，每一层节点个数都可以采取类似的算法。

树的宽度：在树的深度算法基础上，加一个记录访问过的层节点个数最多的变量max,在访问每层前max与last比较，如果max比较大，max不变，如果max小于last，把last赋值给max;

	// 非递归实现
	public int findDeep2(BiTree root) {
		if (root == null)
			return 0;

		BiTree current = null;
		LinkedList<BiTree> queue = new LinkedList<BiTree>();
		queue.offer(root);
		int cur, last;
		int level = 0;
		while (!queue.isEmpty()) {
			cur = 0;// 记录本层已经遍历的节点个数
			last = queue.size();// 当遍历完当前层以后，队列里元素全是下一层的元素，队列的长度是这一层的节点的个数
			while (cur < last)// 当还没有遍历到本层最后一个节点时循环
			{
				current = queue.poll();// 出队一个元素
				cur++;
				// 把当前节点的左右节点入队（如果存在的话）
				if (current.left != null) {
					queue.offer(current.left);
				}
				if (current.right != null) {
					queue.offer(current.right);
				}
			}
			level++;// 每遍历完一层level+1
		}
		return level;
	}

== 二叉树任意两个节点之间路径的最大长度==

算法步骤：

（1）初始化二叉树，并将每个节点Lm和Rm初始化为0，定义二叉树中节点的最大距离Max = -1

（2）为了计算一个节点的Lm和Rm，需要采用后序遍历策略，递归的计算出它左孩子Left的Lm,Rm，Lm = max(Left->Lm + Left->Rm) + 1；和右孩子Right的Lm,Rm，Rm = max(Right->Lm,Right->Rm) + 1；

（3）对于每一个节点，计算Lm + Rm，如果其值大于Max，则Max = Lm + Rm，最后Max就是最大距离。

public class TreeNode {
	int val=0;
	TreeNode left=null;
	TreeNode right=null;
	int maxleft;//左子树最长距离
	int maxright;//右子树最长距离
	public TreeNode(int val) {
		this.val=val;
	}
	 class Solution{
		int max=-1;//最大距离长度
	 public int maxLen(TreeNode root) {
		if (root==null) { //树为空返回0
			return 0;
		}
		if (root.left!=null) {
			root.maxleft=maxLen(root.left)+1;
		}
		if (root.right!=null) {
			root.maxright=maxLen(root.right)+1;
		}
		 //如果以该节点为根节点的子树有最大的距离，那就更新最大的距离
		int sum=root.maxleft+root.maxright;
		if (sum>max) {
			max=sum;
		}
		 return root.maxleft>root.maxright? root.maxleft:root.maxright;
	}
	}
}

<mark>算法题：二叉树层序遍历，进一步提问：要求每层打印出一个换行符</mark>

public class TreeNode {
	int val=0;
	TreeNode left=null;
	TreeNode right=null;
	int maxleft;//左子树最长距离
	int maxright;//右子树最长距离
	public TreeNode(int val) {
		this.val=val;
	}
 class Solution{
 	 //二叉树遍历，要求每层打印出一个换行符
	 public void BST(TreeNode root) {
		if (root==null) {
			return;
		}
		LinkedList<TreeNode> queue=new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			int size=queue.size();
			while (size-->0) {
				TreeNode node=queue.poll();
				System.out.print(node.val+" ");
				if (node.left!=null) {
					queue.offer(node.left);
				}
				if (node.right!=null) {
					queue.offer(node.right);
				}
			}
			System.out.println();
		}
	}
 }
}

<mark>请你说一下，B+树和B-树？</mark>

b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”；

b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（并不慢）；

对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历。

<mark>二叉树 Z 字型遍历</mark>

public class TreeNode {
	int val=0;
	TreeNode left=null;
	TreeNode right=null;
	int maxleft;//左子树最长距离
	int maxright;//右子树最长距离
	public TreeNode(int val) {
		this.val=val;
	}
	
	
}

class Solution{
	//二叉树Z字型遍历
	 public List<List<Integer>> zizagLevelOrder(TreeNode root) {
		List<List<Integer>> resList=new ArrayList<List<Integer>>();
		LinkedList<TreeNode> treeNodes=new LinkedList<>();
		boolean flag=true;//控制反转
		if (root==null) {
			return resList;
		}
		treeNodes.add(root);
		while (treeNodes.size()!=0) {
			flag=!flag;
			int size=treeNodes.size();
			List<Integer> list=new ArrayList<>();
			while (size-->0) {
				TreeNode node=treeNodes.remove();
				list.add(node.val);
				if (node.left!=null) {
					treeNodes.add(node.left);
				}
				if (node.right!=null) {
					treeNodes.add(node.right);
				}
			}
			if (flag) {
				Collections.reverse(list);//反转list列表中元素顺序；
			}
			resList.add(list);
		}
		
		return resList;
	}

}

<mark>编程题：写一个函数，找到一个文件夹下所有文件，包括子文件夹</mark>

import java.io.File;
public class FileCounts {
    public static void main(String[] args) {
        //取得目标目录
        File file = new File("D:");
        //获取目录下子文件及子文件夹
        File[] files = file.listFiles();
        readfile(files);
        
    }
    
    public static void readfile(File[] files) {
        if(files == null) {// 如果目录为空，直接退出 
            return; 
        }
        for(File f:files) {
            //如果是文件，直接输出名字
            if(f.isFile()) {
                System.out.println(f.getName());
            }
            //如果是文件夹，递归调用
            else if(f.isDirectory()) {
                readfile(f.listFiles());
            }
        }
    }
    
}