HashTable

发表于 2018-08-04

HashTable

/**
 * 哈希表
 *
 * @author maxu
 */
public class HashTable<K, V> {
    private static final int upperTol = 10;
    private static final int lowerTol = 2;
    private static final int initCapacity = 7;

    private TreeMap<K, V>[] hashTable;
    private int M;
    private int size;

    public HashTable(int m) {
        M = m;
        size = 0;
        hashTable = new TreeMap[M];
        for (int i = 0; i < M; i++) {
            hashTable[i] = new TreeMap<>();
        }
    }

    public HashTable() {
        this(initCapacity);
    }

    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize() {
        return size;
    }

    public void add(K key, V value) {
        TreeMap<K, V> map = hashTable[hash(key)];
        if (map.containsKey(key)) {
            map.put(key, value);
        } else {
            map.put(key, value);
            size++;
            if (size >= upperTol * M) {
                resize(2 * M);
            }
        }
    }

    public V remove(K key) {
        TreeMap<K, V> map = hashTable[hash(key)];
        V ret = null;
        if (map.containsKey(key)) {
            ret = map.remove(key);
            size--;
            if (size < lowerTol * M && M / 2 > initCapacity) {
                resize(M / 2);
            }
        }
        return ret;
    }

    private void resize(int newM) {
        TreeMap<K, V>[] newHashTable = new TreeMap[newM];
        for (int i = 0; i < newM; i++) {
            newHashTable[i] = new TreeMap<>();
        }
        int oldM = M;
        this.M = newM;
        for (int i = 0; i < oldM; i++) {
            TreeMap<K, V> map = hashTable[i];
            for (K k : map.keySet()) {
                newHashTable[hash(k)].put(k, map.get(k));
            }
        }
        this.hashTable = newHashTable;
    }

    public void set(K key, V value) {
        TreeMap<K, V> map = hashTable[hash(key)];
        if (!map.containsKey(key)) {
            throw new IllegalArgumentException(key + "doesn't exist!");
        }
        map.put(key, value);
    }

    public boolean contains(K key) {
        return hashTable[hash(key)].containsKey(key);
    }

    public V get(K key) {
        TreeMap<K, V> map = hashTable[hash(key)];
        if (!map.containsKey(key)) {
            throw new IllegalArgumentException(key + "doesn't exist!");
        }
        return map.get(key);
    }
}

处理哈希冲突

开放地址法（线性探测，平方探测）
链地址法
再哈希法
建立公共溢出区

Git使用

发表于 2018-07-14

阅读全文 »

Liunx

发表于 2018-07-10

阅读全文 »

线程和进程

发表于 2018-06-29

线程与进程

概念

进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位.
线程一个进程内部可能包含了很多顺序执行流，每个顺序执行流就是一个线程。 线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源[一块内存空间和一组系统资源]

阅读全文 »

Set实现

发表于 2018-06-23

// 应用：客户统计、词汇量统计
public interface Set<E> {
    void add(E e); // 不能添加重复元素
    void remove(E e);
    boolean contains(E e);
    int getSize();
    boolean isEmpty();
}

阅读全文 »

同步、异步、阻塞、非阻塞

发表于 2018-06-22

阻塞与非阻塞

概念

阻塞和非阻塞这两个概念与程序（线程）等待消息通知(无所谓同步或者异步)时的状态有关。也就是说阻塞与非阻塞主要是程序（线程）等待消息通知时的状态角度来说的。

阻塞调用是指调用结果返回之前，当前线程会被挂起，一直处于等待消息通知，不能够执行其他业务。函数只有在得到结果之后才会返回。

对于同步调用来说，很多时候当前线程可能还是激活的，只是从逻辑上当前函数没有返回而已，此时，这个线程可能也会处理其他的消息
非阻塞指在不能立刻得到结果之前，该函数不会阻塞当前线程，而会立刻返回

虽然表面上看非阻塞的方式可以明显的提高CPU的利用率，但是也带了另外一种后果就是系统的线程切换增加。增加的CPU执行时间能不能补偿系统的切换成本需要好好评估。

同步与异步

概念

同步:所谓同步就是一个任务的完成需要依赖另外一个任务时，只有等待被依赖的任务完成后，依赖的任务才能算完成，这是一种可靠的任务序列。要么成功都成功，失败都失败，两个任务的状态可以保持一致。
异步: 异步是不需要等待被依赖的任务完成，只是通知被依赖的任务要完成什么工作，依赖的任务也立即执行，只要自己完成了整个任务就算完成了。至于被依赖的任务最终是否真正完成，依赖它的任务无法确定，所以它是不可靠的任务序列。
消息通知: 异步的概念和同步相对。当一个同步调用发出后，调用者要一直等待返回消息（结果）通知后，才能进行后续的执行；当一个异步过程调用发出后，调用者不能立刻得到返回消息（结果）。实际处理这个调用的部件在完成后，通过状态、通知和回调来通知调用者。

这里提到执行部件和调用者通过三种途径返回结果：状态、通知和回调。使用哪一种通知机制，依赖于执行部件的实现，除非执行部件提供多种选择，否则不受调用者控制。

阻塞与非阻塞，和同步异步无关，可以阻塞等待同步执行过程完成，也可以阻塞等待异步执行过程完成。根据以上理解, 阻塞与非阻塞/同步与异步是可以相互组合的。

同步阻塞

调用者发起IO操作请求，等待IO操作完成再返回。IO操作的过程需要等待，操作执行完成后返回结果。
同步非阻塞调用者发起IO操作请求，询问IO操作的状态，如果未完成，则立即返回；如果完成，则返回结果。IO操作的过程需要等待执行完成才返回结果。
异步阻塞调用者发起IO操作请求，等待IO操作完成再返回。IO操作的过程不需要等待，操作完成后通过通知或回调获得结果。

首先需要明确：异步操作是可以被阻塞住的，只不过它不是在处理消息时阻塞，而是在等待消息通知时被阻塞。
异步非阻塞调用者发起IO操作请求，询问IO操作的状态，如果未完成，则立即返回；如果完成，则返回结果。IO操作的过程不需要等待，操作完成后通过通知或回调获得结果。

举例

鄙人很爱看电影，于是乎就拿下载电影来说事儿吧O(∩_∩)O哈哈~

同步阻塞：我一直抱着ipad，盯着它的下载进度条，直到 100% 才算完成。

同步体现：等待下载完成通知；

阻塞体现在：等待下载完成通知过程中，不能做其他任务处理。

同步非阻塞：我点击下载任务后就去洗衣服(嗯，我还是很勤劳滴~),每过一段时间就去瞄一眼进度条，看到100%就算完成。

同步体现在：等待下载完成通知

非阻塞体现在：等待下载完成通知过程中，去干别的任务了，只是时不时会瞄一眼进度条。

异步阻塞我换了个有下载完成通知功能的软件，下载完成就“叮”一声。不过我仍然一直等待“叮”的声音 [似不似很傻(⊙o⊙)…]。

异步体现在：下载完成“叮”一声通知；

阻塞体现在：等待下载完成“叮”一声通知过程中，不能做其他任务处理；

异步非阻塞：仍然是那个会“叮”一声的下载软件，我提交下载任务后就去干别的，听到“叮”的一声就知道完成了。

异步体现在：下载完成“叮”一声通知；

非阻塞体现在：等待下载完成“叮”一声通知过程中，去干别的任务了，只需要接收“叮”声通知即可；[软件处理下载任务，我处理其他任务，不需关注进度，只需接收软件“叮”声通知，即可]

Binary Search Tree

发表于 2018-06-22

Binary Search Tree

必须有可比较性
左孩子比根节点小，右孩子比根节点大
如果想包含重复的元素的话，只需要定义：左子树小于等于节点；或者右子树大于等于节点

实现

public class BST<E> extends Comparable<E> {
	private class Node {
		public E e;
		public Node left, right;
	}

	public Node(E e) {
		this.e = e;
		this.left = null;
		this.right = null;
	}

	private Node root;
	private int size;

	public BST() {
		this.root = null;
		this.size = 0;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}
	// 添加元素
	public void add(E e) {
		// if(root == null) {
		// 	root = new Node(e);
		// 	size ++;
		// } else {
		// 	add(root,e);
		// }
		
		// 修改之后
		root = add(root,e);
	}

	// 向以node为根的二分搜索树种插入元素E
	private Node add(Node node, E e) {
		// if(root.e.equals(e)) {
		// 	return;
		// } else if(e.compareTo(node.e) < 0 && node.left == null) {
		// 	node.left = new Node(e);
		// 	size ++;
		// 	return;
		// } else if(e.compareTo(node.e) > 0 && node.right == null) {
		// 	node.right = new Node(e);
		// 	size ++;
		// 	return;
		// }
		// if (e.compareTo(node.e) < 0) {
		// 	add(node.left,e);
		// } else {
		// 	add(node.right,e);
		// }

		// 当我们递归到null的时候就一定要创建一个节点
		if(node == null) {
			size ++;
			return new Node(e);
		}
		if (e.compareTo(node.e) < 0) {
			node.left = add(node.left,e);
		} else {
			node.right = add(node.right,e);
		}
		return node;
	}

	public boolean contains(E e) {
		return contains(root, e);
	}

	private boolean contains(Node node, e) {
		if(node == null) {
			return false;
		}

		if(e.compareTo(node.e)){
			return true;
		}

		if (e.compareTo(node.e) < 0) {
			return contains(node.left,e);
		} else {
			return contains(node.right,e);
		}
	}

	// 二叉树的前序遍历
	public void preOrder() {
		preOrder(root);
	}

	private void preOrder(Node node) {
		if(node == null) {
			return;
		}
		System.out.println(node.e);
		preOreder(node.left);
		preOreder(node.right);
	}

	// 顺序的排列的
	public void inOrder() {
		inOrder(root);
	}

	public void inOrder(Node node) {
		if(node == null) {
			return;
		}
		preOreder(node.left);
		System.out.println(node.e);
		preOreder(node.right);
	}

	// 后序遍历
	// 为二分搜索释放内存
	public void postOrder() {
		postOrder(root);
	}

	private void postOrder(Node node) {
		if(node == null) {
			return;
		}
		preOreder(node.left);
		preOreder(node.right);
		System.out.println(node.e);
	}
    // 最小值
    public E minimum() {
        if(size == 0){
            throw new IllegalArgumentException("BST is empty");
        }
        return minimum(root).e;
    }
    // 返回已node为根的二分搜索树的最小值所在的节点
    private Node minimum(Node node) {
        if(node.left == null) {
            return node;
        }
        return minimum(node.left);
    }
    
    // 最大值	
    public E maximum() {
        if(size == 0){
            throw new IllegalArgumentException("BST is empty");
        }
        return maximum(root).e;
    }
    // 返回已node为根的二分搜索树的最小值所在的节点
    private Node maximum(Node node) {
        if(node.right == null) {
            return node;
        }
        return minimum(node.right);
    }
    // 从树中删除最小值
    public E removeMin() {
        E ret = minimum();
        // 返回删除后新的根节点
        root = removeMin(root);
        return ret;
    }
    // 返回删除节点后新的二分搜索树
    private Node removeMin(Node node) {
        
        if(node.left == null) {
            Node rightNode = node.rigth;
            node.right = null;
            size --;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }
    
     // 从树中删除最小值
    public E removeMax() {
        E ret = maximum();
        // 返回删除后新的根节点
        root = removeMax(root);
        return ret;
    }
    // 返回删除节点后新的二分搜索树
    private Node removeMax(Node node) {
        
        if(node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size --;
            return leftNode;
        }
        node.right = removeMin(node.right);
        return node;
    }
    
    // 删除某一结点
    public void remove(E e) {
        root = remove(root);
    }
    private Node remove(Node node, E e) {
        if(node == null) {
            return null;
        }
        if(e.compareTo(node.e) < 0) {
            node.left = remove(node.left,e);
            return node;
        } else if(e.compareTo(node.e) > 0) {
            node.right = remove(node.right,e);
            return node;
        } else {
            // 3种情况
            if(node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }
            if(node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }
            // 当左右子树都不为空的时候
            Node successor = minimum(node.right);
            // 这里我们进行了删除size进行了减操作
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right = null;
            return successor;
        }
    }
}

前序遍历非递归实现

// 首先将节点压入栈中，如果栈不为空这弹出栈顶元素，并将左右孩子压入栈中，首先压入左孩子然后压入右孩子
public void preOrder() {
  Stack<Node> stack = new Stack<>();
  stack.push(root);
  if(!stack.isEmpty()){
    Node node = stack.pop();
    System.out.println(node.e);
    if(node.left != null){
      stack.push(node.left);
    }
    if(node.right != null){
      stack.push(node.right);
    }
  }
}

层序遍历实现

// 利用队列
public void levelOrder() {
  Queue<Node> q = new LinkedList<>();
  q.add(root);
  while(!q.isEmpty()) {
    Node cur = q.remove();
    System.out.println(cur.e);
    if(cur.left != null) {
      q.add(cur.left);
    }
    if(cur.right != null) {
      q.add(cur.right);
    }
  }
}

链表应用

发表于 2018-06-19

链表实现栈

public class LinkedListStack<E> implements Stack<E> {

	private LinkList<E> list;
	public LinkedListStack() {
		list = new LinkList<>();
	}
	@Override
	public void push(E e) {
		list.addFirst(e);
	}

	@Override
	public E pop() {
		return list.removeFirst();
	}

	@Override
	public E peek() {
		return list.getFirst();
	}

	@Override
	public int getSize() {
		return list.getSize();
	}

	@Override
	public boolean isEmpty() {
		return list.isEmpty();
	}
	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		res.append("Stack:top");
		res.append(list);
		return res.toString();
	}
}

链表实现队列

public class LinkedListQueue<E> implements Queue<E> {
	private class Node {
 		public E e;
    	public Node next;

		public Node(E e,Node next) {
			this.e = e;
			this.next = next;
		}

		public Node(E e) {
			this(e,null);
		}
		public Node() {
			this(null,null);
		}
		public String toString() {
			return e.toString();
		}
	}

	private Node head, tail;
	private int size;

	public LinkedListQueue() {
		head = null;
		tail = null;
		size = 0;
	}
	public int getSize() {
		return size;
	}
	public boolean isEmpty() {
		return size == 0;
	}
	public void enqueue(E e) {
		if(tail == null) {
			tail = new Node(e);
			head = tail;
		} else {
			tail.next = new Node(e);
			tail = tail.next;
		}
		size ++;
	}
	public void dequeue() {
		if(isEmpty()) {
			throw new IllegalArgumentException("Cannot dequeue from an empty queue");
		}
		Node reNode = head;
		head = head.next;
		retNode.next = null;
		if(head == null) {
			tail = null;
		}
		size --;
		return retNode.e;
	}
}

链表与递归

移除链表元素
删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

public class Solution {

	public ListNode removeElements(ListNode head, int val) {
    // 创建虚拟节点
		ListNode dummyHead = new ListNode(0);
		dummyHead.next = head;
    for(ListNode pre = dummyHead; pre.next != null;) {
      	if(pre.next.val == val) {
          pre.next = pre.next.next;
        } else {
          pre = pre.next;
        }
    }
	}
}

把递归过程想成一个子函数，在子函数中写处理逻辑来解决上层函数的问题。

public class Solution {

	public ListNode removeElements(ListNode head, int val) {
		if(head == null){
			return null;
		}
		head.next = removeElements(head.next,val);
		return head.val == val? head.next: head;
	}
}

实现LinkedList

发表于 2018-06-17

数据存储在节点中

class Node {
    E e;
    Node next;
}

优点：不需要处理固定容量的问题，做到真正的动态
缺点：丧失了随机访问的能力

阅读全文 »

实现Stack

发表于 2018-06-15

public interface Stack<E> {
    void push(E e);
    E pop();
    E peek();
    int getSize();
    boolean isEmpty();
}

阅读全文 »