public class BinarySearchTree {static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}}public TreeNode root;public boolean search(int key){TreeNode cur = root;if(root == null){return false;}while(cur != null){if(cur.val > key){cur = cur.left;} else if (cur.val <key) {cur = cur.right;}else{return true;}}return false;}public boolean insert(int key){TreeNode node = new TreeNode(key);if(root == null){//  如果根就是的話，直接添加了，然后return true；root = node;return true;}TreeNode cur = root;TreeNode parent = cur;//賦值while(cur != null){if(cur.val < key){parent = cur;  //這一步一定要提前cur = cur.right;} else if (cur.val >key) {parent = cur;cur = cur.left;}else{return false;}}if(parent.val < key){   //你就說為什么cur == null了把它小于的話(cur在該添加的位置上面等于了null)parent.right = node;}else{parent.left = node;}return true;}

    public void remove(int val){TreeNode cur = root;//要移除這個節點，首先我要先遍歷二叉搜索樹找到這個節點TreeNode parent = null;if(root == null){return;}while(cur != null)if(cur.val < val) { parent = cur;cur = cur.right;}else if(cur.val > val){parent = cur;cur = cur.left;}else{//要刪除的節點，找到了removeTreeNode(cur,parent);}}private void removeTreeNode(TreeNode cur,TreeNode parent) {if(cur.left == null){if(cur.val > parent.val){//這一步就純純的是判讀那cur走到了parent的左邊還是右邊，parent.right = cur.right;//你這一點都不知道，我滴媽你讓parent的左邊接力還是右邊？}else{parent.left = cur.right;}}else if(cur.right == null){       //cur的右邊空了if(cur.val > parent.val){//和上面一樣parent.right = cur.left;}else{parent.left = cur.left;}}else{    // cur 的兩邊都不為空TreeNode target = cur.right; //準備TreeNode parentTarget = null;while(target.left != null){parentTarget = target;target = target.left;}cur.val = target.val;if(parentTarget != null){parentTarget.left = target.right;}else{cur.right = target.right;}}}

2.3?模型

比如：

統計文件中每個單詞出現的次數，統計結果是每個單詞都有與其對應的次數： < 單詞，單詞出現的次數 >

import java.util.Collection;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;public class Test {public static void main(String[] args) {Map<String,Integer> map = new TreeMap<>();
//1.put 和 get(Object key) 返回 key 對應的 valuemap.put("zhangsan",18);map.put("zhangsan",20);//會進行更新，key值不會重復map.put("lisi",18);map.put("wangWu",50);//int val = map.get("lihua");返回的是一個空指針異常而不是類型轉換異常，很有講究的//這個時候就可以用這個方法map.getOrDefault("lihua",20);// 沒有key的話就相當于一次put，（key是lihua）（val是20）
//3.(keyset):Set<K> keySet() 返回所有 key 的不重復集合Set<String> set = map.keySet();  //經過排序的從大到小for (String s: set) {System.out.print(s + " ");}//或者System.out.println(set);
//4：Set<K> keySet() 返回所有 key 的不重復集合Collection<Integer> collection = map.values();//也是有順序的，一般都是按照key的進行排序System.out.println(collection);System.out.println("==============");
//5:Set<Map.Entry<K, V>> entrySet() 返回所有的 key-value 映射關系Set<Map.Entry<String,Integer>> entries = map.entrySet();for (Map.Entry<String,Integer> entry:entries) {System.out.println("key:" + entry.getKey() + " val:" + entry.getValue());}//或者直接打印也行System.out.println(entries);System.out.println("===========");}

? ? ? ?1.? 哈希函數的定義域必須包括需要存儲的全部關鍵碼，而如果散列表允許有m個地址時，其值域必須在0到m-1之間（我是數組我要連續(*^▽^*)）

? ? ? 2.? 哈希函數計算出來的地址能均勻分布在整個空間中

? ? ? 3.哈希函數應該比較簡單

// key-value 模型
public class HashBucket {public static class Node {private int val;private int key;public Node next;//這里一定要注意，你如果在這里上來就構造了一個根節點的public Node(int key, int val) {this.key = key;this.val = val;}}private static final double LOAD_FACTOR = 0.75;//負載因子//根本不需要根節點，我底層是數組進行實現的，要你沒有用//public Node root;public Node[] array = new Node[5];    //我這個就是HsahMap的底層實現，開散列：數組 + 鏈表private int usedSize;   //一般只要一個數據結構底層運用了數組，一般都會有usedSize去記錄有效元素public boolean search(int key) {   //這個要判斷val嗎？int index = key % array.length;Node cur = array[index];//   我直接計算出這個key應該在的位置，然后在數組的這個位置進行查找while (cur != null) {if (cur.key == key) {return true;}cur = cur.next;}return false;}public void put(int key, int val) {int index = key % array.length;Node cur = array[index];while (cur != null) {  // 先遍歷一遍這個鏈表，判讀這個key在不在里面，如果在的話，就更新val值if (cur.key == key) {cur.val = val;}cur = cur.next;}//走到這里說明不在這里，直接進行頭插Node node = new Node(key,val);node.next = array[index];array[index] = node;usedSize++;if(usedSize * 1.0/ array.length > LOAD_FACTOR){  //這里要乘  1.0revise(array);}}private void revise(Node[] array) {  //這里要是有參數的話，下面的array，一定要加this啊！！！！！！！！！！！//首先讓數字進行擴容//最后再返回數組Node[] tmpArray = Arrays.copyOf(array,2*array.length);//先遍歷一遍原來的數組，再在每個數組元素上遍歷鏈表for (int i = 0; i < array.length; i++) {Node cur = array[i];while(cur != null){//計算出新的下標，再進行頭插int newIndex = cur.key % tmpArray.length;//這個節點就是cur其實沒必要再多定義了/*Node node = new Node(cur.key,cur.val);node.next = tmpArray[newIndex];tmpArray[newIndex] = node;cur = cur.next;
*///你們是一樣的道理Node curNext = cur.next;cur.next = tmpArray[newIndex];tmpArray[newIndex] = cur;cur =curNext;}}array = tmpArray;//   這里一定要this啊！！！！！！！！！！！！！//  除非上面沒有參數}public int get(int key){int index = key % array.length;Node cur = array[index];//   我直接計算出這個key應該在的位置，然后在數組的這個位置進行查找while (cur != null) {if (cur.key == key) {return cur.val;}cur = cur.next;}return -1;}
}

public class Test {public static void main(String[] args) {HashBucket hashBucket = new HashBucket();hashBucket.put(1,1);hashBucket.put(2,2);hashBucket.put(3,3);hashBucket.put(4,4);hashBucket.put(5,5);//就這里i = 1下標出問題了System.out.println("===============");System.out.println(hashBucket.get(1));System.out.println(hashBucket.get(2));System.out.println(hashBucket.get(5));System.out.println(hashBucket.get(9));}
}

class Person{String name;public Person(String name) {this.name = name;}//一定要重寫equals方法，因為我要看看你一開始在不在里面，相同名字的lihua@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Person person = (Person) o;return Objects.equals(name, person.name);}//這個也是@Overridepublic int hashCode() {return Objects.hash(name);}
}public class HashBucket1 <K,V>{public class Node<K,V>{  //為什么不能是靜態的？（靜態的不依賴于類，所以說我根本不知道K,V是誰？private K key;private V val;private Node<K,V> next;//這里一定要注意，你如果在這里上來就構造了一個根節點的public Node( K key, V val) {this.key = key;this.val = val;}}private Node[] array ;private static final double LOAD_FACTOR = 0.75;//負載因子public HashBucket1() {this.array = new Node[10];}private int usedSize;public void put(K key, V val){int hash = key.hashCode();//還能是負的？int index = Math.abs(hash % array.length);Node<K,V> cur = array[index];//先找一遍看有沒有，沒有直接頭插法while(cur != null){if(cur.key.equals(key)){   //所以說這個key一定要重寫equals方法cur.val = val;return;}cur = cur.next;}// 到這里就肯定沒有了，沒有直接頭插法Node<K,V> node = new Node<>(key,val);node.next = array[index];array[index] = node;usedSize++;// 判斷負載因子大不大if(usedSize*1.0 / array.length > LOAD_FACTOR){revise();}}private void revise() {Node<K,V> [] tmpArray = Arrays.copyOf(array,2*array.length);for (int i = 0; i < array.length; i++) {Node<K,V> cur = array[i];while(cur != null){Node<K,V> curNext = cur.next;//找到新下標直接進行插入int newIndex = Math.abs(cur.hashCode() % tmpArray.length);cur.next = tmpArray[newIndex];tmpArray[newIndex] = cur;cur = curNext;}}this.array = tmpArray;}public V get(K key){int index = key.hashCode() % array.length;Node<K,V> cur = array[index];while(cur != null){if(cur.key == key){return cur.val;}cur = cur.next;}return null;}public boolean search(K key){int index = key.hashCode() % array.length;Node<K,V> cur = array[index];while(cur != null){if(cur.key == key){return true;}cur = cur.next;}return false;}
}

public class TestHashBucket1 {public static void main(String[] args) {Person person = new Person("zhangSan");Person person1 = new Person("zhangSan");Person person2 = new Person("zhangSan");HashBucket1<Person,Integer> hashBucket1= new HashBucket1();//這個key一定要重寫equals方法（不然俺咋判斷，我寫的哈希表里面有沒有這個元素hashBucket1.put(person,18);hashBucket1.put(person1,18);hashBucket1.put(person2,18);System.out.println("============");}
}

class Solution {public int singleNumber(int[] nums) {Set<Integer> set = new HashSet<>();
//一邊進去，相同的出來for(int i = 0; i < nums.length; i++){if(set.contains(nums[i])){set.remove(nums[i]);}else{set.add(nums[i]);}}
//如果包含就是你了（只出現過一次）for(int i = 0; i < nums.length; i++){if(set.contains(nums[i])){return nums[i];}}return -1;}
}

import java.util.Map;
class Solution {public Node copyRandomList(Node head) {Node cur = head;Map<Node,Node> map = new HashMap<>();while(cur != null){Node node = new Node(cur.val);map.put(cur,node);   //幫下面的鏈接上，通過HashMapcur = cur.next;//node = node.next;       這樣寫肯定不對，因為我每次都要new一個Node對象，就鏈接不上了}cur = head;while(cur != null){map.get(cur).random = map.get(cur.random);map.get(cur).next = map.get(cur.next);cur = cur.next;}return map.get(head);}
}

class Solution {public int numJewelsInStones(String jewels, String stones) {Set<Character> set = new HashSet<>();for(int i = 0; i<jewels.length(); i++){set.add(jewels.charAt(i));   //    是add而不是put}int count = 0;for(int i = 0; i<stones.length(); i++){char ch = stones.charAt(i);if(set.contains(ch)){count++;}}return count;}
}

 public static void find(String s1,String act){Set<Character> set = new HashSet<>();for (char ch: act.toUpperCase().toCharArray()) {set.add(ch);}Set<Character> set2 = new HashSet<>();for (char ch: s1.toUpperCase().toCharArray()) {if(! set.contains(ch)){set2.add(ch);}}for (Object o:set2.toArray()) {System.out.println(o);}}public static void main(String[] args) {String s1 = "abc def 7 abc";String s2 = "abc";find(s1,s2);}

public  List<String> topKFrequent(String[] words, int k) {// 一個哈希表，統計所有單詞出現的個數Map<String,Integer> map = new HashMap<>();for(String word : words){if( !map.containsKey(word)){map.put(word,1);}else{int count =  map.get(word);map.put(word,++count);}}//建立小根堆，重寫比較方法//  這里的Entry<>記得前面加上Map，因為他是Map里面的內部類，所有的都要加PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {@Overridepublic int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {if((o1.getValue() - o2.getValue()) == 0 ){return o2.getKey().compareTo(o1.getKey());}return o2.getValue() - o1.getValue();}});for (Map.Entry<String,Integer> entry : map.entrySet()) {Map.Entry<String,Integer> top =  minHeap.peek();if(minHeap.size() <= k){minHeap.offer(entry);}else{//   如果你倆的出現的頻率相同，讓字母的ASCII碼值進行比較大的進來if(top.getValue().equals(entry.getValue())){if(top.getKey().compareTo(entry.getKey()) > 0){minHeap.poll();minHeap.offer(entry);}}else{// 下一個元素的val大，讓下一個元素進來if(entry.getValue().compareTo(top.getValue()) > 0){minHeap.poll();minHeap.offer(entry);}}}}List<String> ret = new ArrayList<>();for (int i = 0; i < k; i++) {Map.Entry<String,Integer> top = minHeap.poll();ret.add(top.getKey());}Collections.reverse(ret);return ret;}