1、冒泡排序
for(int i=0;i<n;i++){
for(int j=0;j<n-1-i;j++){
if(temp[j]>temp[j+1]){
int t=temp[j];
temp[j]=temp[j+1];
temp[j+1]=t;
}
}
}
2、快速排序
public void quicksort(int[] array,int left,int right){
if(left<right){
int key = array[left];
int low = left;
int high = right;
while(low<high){
while(low<high && array[high]>=key){
high--;
}
array[low] = array[high];
while(low<high && array[low]<=key){
low++;
}
array[high] = array[low];
}
array[low] = key;
quicksort(array,left,low-1);
quicksort(array,low+1,right);
}
}
3、一致性hash
一致性hash算法可以解决容错性和扩展性的问题。
系统中增加更多的虚拟节点，可以更好的解负载均衡问题。
public class Shard<S> { // S类封装了机器节点的信息 ，如name、password、ip、port等
private TreeMap<Long, S> circle; // 将整个hash值空间组成一个虚拟的环
private List<S> shards; // 真实机器节点
private final int NODE_NUM = 100; // 每个机器节点关联的虚拟节点个数
private final HashFunction hashFunction; // 选择一个碰撞率低的hash()函数
public Shard(List<S> shards,HashFunction hashFunction) {
super();
this.shards = shards;
this.hashFunction = hashFunction;
init();
}
private void init() { // 初始化一致性hash环
circle = new TreeMap<Long, S>();
for (int i = 0; i<shards.size(); ++i) { // 每个真实机器节点都需要关联虚拟节点
final S shardInfo = shards.get(i);
add(shardInfo);
}
}
public void add(S node) {
for (int i = 0; i < NODE_NUM; i++) {
// 虚拟节点用一些特定的hash值来替代，这样形成了hash值到真实节点的映射
circle.put(hashFunction.hash(node.toString() + i), node);
}
}
public void remove(S node) {
for (int i = 0; i < NODE_NUM; i++) {
// 移除真实节点下对应的所有虚拟节点（特定的一些hash值）
circle.remove(hashFunction.hash(node.toString() + i));
}
}
public S getShardInfo(String key) {
// SortedMap<Long, S> tail = circle.tailMap(hash(key)); // 沿环的顺时针找到一个虚拟节点
// if (tail.size() == 0) {
// return circle.get(circle.firstKey());
// }
// return tail.get(tail.firstKey()); // 返回该虚拟节点对应的真实机器节点的信息
if (circle.isEmpty()) {
return null;
}
Long hash = hashFunction.hash(key);
// 如果当前hash值没有定位到虚拟节点
if (!circle.containsKey(hash)) {
SortedMap<Long, S> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
}
class Machine {
String ip;
String name;
public Machine(String ip, String name) {
this.ip = ip;
this.name = name;
}
public String getIp() {
return ip;
}
public void setIp(String ip) {
this.ip = ip;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
public class Test {
public static void main(String[] args) {
Machine a = new Machine("192.168.0.1", "a");
Machine b = new Machine("192.168.0.2", "b");
Machine c = new Machine("192.168.0.3", "c");
List<Machine> list = Arrays.asList(a, b, c);
Map<String, Integer> map = new HashMap<String, Integer>();
Shard<Machine> mcs = new Shard<Machine>(list, new HashFunction());
// 存储0到2000个数，看存储在各个机器上的数的数量是否大致均匀
for (int i = 0; i < 2000; i++) {
String key = i + "";
Machine m = mcs.getShardInfo(key);
if (map.get(m.getIp()) == null) {
map.put(m.getIp(), 0);
} else {
map.put(m.getIp(), (int) map.get(m.getIp()) + 1);
}
}
Iterator<Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Entry<String, Integer> entry = iterator.next();
System.out.println(entry.getKey() + "/" + entry.getValue());
}
}
}
某次运行后的结果如下：
192.168.0.2/599 192.168.0.1/698 192.168.0.3/700
4、LRU最近最少使用算法
要效率的话使用hash搜索，要实现最近最少的话就用双向链表
public class LRUCache {
private int cacheSize;
private HashMap<Object, Entry> nodes; // 缓存容器 ,为了提高查询速度需要这个结构
private int currentSize;
private Entry first; // 链表头
private Entry last; // 链表尾
static class Entry {
Entry prev;
Entry next;
Object key;
Object value;
}
public LRUCache(int i) {
currentSize = 0;
cacheSize = i;
nodes = new HashMap<Object, Entry>(i);
}
/**
* 获取缓存中对象,并把它放在最前面
*/
public Entry get(Object key) {
Entry node = nodes.get(key);
if (node != null) {
moveToHead(node);
return node;
} else {
return null;
}
}
/**
* 添加 entry到hashtable, 并把entry
*/
public void put(Object key, Object value) {
//先查看hashtable是否存在该entry, 如果存在，则只更新其value
Entry node = nodes.get(key);
if (node == null) {
//缓存容器是否已经超过大小.
if (currentSize >= cacheSize) {
nodes.remove(last.key);
removeLast();
} else {
currentSize++;
}
node = new Entry();
}
node.value = value;
//将最新使用的节点放到链表头，表示最新使用的.
moveToHead(node);
nodes.put(key, node);
}
/**
* 将entry删除, 注意：删除操作只有在cache满了才会被执行
*/
public void remove(Object key) {
Entry node = nodes.get(key);
//在链表中删除
if (node != null) {
if (node.prev != null) {
node.prev.next = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
}
if (last == node)
last = node.prev;
if (first == node)
first = node.next;
}
//在hashtable中删除
nodes.remove(key);
}
/**
* 删除链表尾部节点，即使用最后 使用的entry
*/
private void removeLast() {
//链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）
if (last != null) {
if (last.prev != null){
last.prev.next = null;
}
else{
first = null;
}
last = last.prev;
}
}
/**
* 移动到链表头，表示这个节点是最新使用过的
*/
private void moveToHead(Entry node) {
if (node == first)
return;
if (node.prev != null)
node.prev.next = node.next;
if (node.next != null)
node.next.prev = node.prev;
if (last == node)
last = node.prev;
if (first != null) {
node.next = first;
first.prev = node;
}
first = node;
node.prev = null;
if (last == null){
last = first;
}
}
/*
* 清空缓存
*/
public void clear() {
first = null;
last = null;
currentSize = 0;
}
}