散列表类似于数组，可以把散列表的散列值看成数组的索引值，访问散列表和访问数组元素一样快速，他可以在常数时间内实现查找和插入操作。 由于无法通过散列值知道键的大小，因此散列表无法实现有序性操作。 散列函数 对于一个大小为M的散列表，散列函数能够把任意的数转换成【0，M-1】内的正整数，该正整数即为hash值。 散列表存在冲突，也就是两个不同的键可能有相同的hash值。 散列函数应该满足三个条件： 一致性：相等的键应当有相等的hash值，两个键相等表示调用equals返回的值相等 高效性：计算应当简便，有必要的话可以把hash值缓存起来，在调用hash函数时直接返回。 均匀性：所有键的ha...

2-3查找树引入2-节点和3-节点，目的为了让树平衡。一颗完美平衡的2-3查找树的所有空链接到根节点的距离应该是相同的。  插入操作 插入操作和BST的插入操作有很大区别，BST的插入操作是先进行一次未命中的查找，然后再将节点插入到对应的空链表上，但是2-3查找树如果也这么做的话，那么就会破坏平衡性。它是将新节点到叶子节点上。 根据叶子节点的类型不同，有不同的处理方式： 如果插入到2-节点上，那么直接变成3-节点。 如果插入到3-节点上，那么暂时先变成4-节点，转成三个2-节点，并将中间的节点加入上层节点，如果上层节点也变成了4-那就继续拆分。       性质： 2-3查找树的插入操作都是局...

概念 首先我们要了解二叉树和二叉查找树的概念 二叉树是一个空连接，可以有左右子树，每个链接都能指向自己的子树。 二叉查找树 每个节点的值都大于等于左子树的所有节点，小于等于右子树的所有节点。 BST有个重要性质：中序遍历递增。 方法get 如果树是空的返回空 如果相等，直接返回 小于，递归左子树 大于，递归右子树 方法put 如果root为空，新建一个 如果插入的存在，覆盖 不存在，新建一个，然后递归放到合适的位置。 分析 二叉树算法的运行时间取决于树的高度，最好的情况是一颗完全二叉树O(logN)，最坏的情况是一条线N 方法floor floor(key)，找到小于这个键的最大键 当小于根节...

介绍 符号表是一种键值对的数据结构，可以快速查找 分为有序和无序两种。 有序的可以实现min,max,根据键的大小来实现的操作。所以需要实现Compareable接口。 链表实现无序符号表 import javax.xml.soap.Node; public class ListUnorderedST<Key,Value> implements UnorderedST<Key,Value> { private Node first; private class Node{ Key key; Value value; Node next; Node(Key key,Val...

栈的实现方式 ##数组实现 public interface MyStack<Item> extends Iterable<Item>{ MyStack<Item> push(Item item); Item pop() throws Exception; boolean isEmpty(); int size(); } import java.util.Iterator; public class ArrayStack<Item> implements MyStack<Item> { //栈元素数组只能通过转型来创建泛型数组 pri...

#排序模板 public abstract class Sort<T extends Comparable<T>> { public abstract void sort(T[] nums); protected boolean less(T v,T w){ return v.compareTo(w)<0; } protected void swap(T[] a,int i,int j){ T t=a[i]; a[i]=a[j]; a[j]=t; } } ##选择排序 /** * 选择排序：选出最小的一个放到第一个位置，再在第二个位置选出最小的 * 放到第二个位置...

package com.nowcoder.service; import org.apache.commons.lang.CharUtils; import org.apache.commons.lang.StringUtils; import org.slf4j.Logger; import org.slf4j.LoggerFactory; import org.springframework.beans.factory.InitializingBean; import org.springframework.stereotype.Service; import java.io.Buffer...