从几十W的IP库中，判断某条IP是否存在
以IPV4举例，IPv4使用32位（4字节）地址，假设库中存的是点分十进制数据
方法
（1）：将点分十进制数转化为long，排序后进行二分查找，如果只查一次的话，复杂度较大，查的次数多比较划算
（2）：使用布隆过滤器，适合查不存在的数据，查存在的数据不一定准确，有误差，但是效率高
（3）：将数据转化为二进制，建立一颗01二叉树，然后查找
public class IPUtil {
// 用于高位对应
public long ip2Long(String ipString) {
String[] ipSlices = ipString.split("\.");
long rs = 0;
for (int i = 0; i < ipSlices.length; i++) {
long longSlice = Long.parseLong(ipSlices[i]) << (8 * i);
rs = rs | longSlice;
}
return rs;
}
// 用于压缩数据
public int ip2Int(String ipString) {
// 取 ip 的各段
String[] ipSlices = ipString.split("\.");
int rs = 0;
for (int i = 0; i < ipSlices.length; i++) {
// 将 ip 的每一段解析为 int，并根据位置左移 8 位
int intSlice = Integer.parseInt(ipSlices[i]) << (8 * i);
// 或运算
rs = rs | intSlice;
}
return rs;
}
public String int2Ip(int ipInt) {
String[] ipString = new String[4];
for (int i = 0; i < 4; i++) {
// 每 8 位为一段，这里取当前要处理的最高位的位置
int pos = i * 8;
// 取当前处理的 ip 段的值
int and = ipInt & (255 << pos);
// 将当前 ip 段转换为 0 ~ 255 的数字，注意这里必须使用无符号右移
ipString[i] = String.valueOf(and >>> pos);
}
return String.join(".", ipString);
}
}
java手写Hashmap简易实现，实现get put resize功能
public class MyhashMap {
static class Node {
private Object key;
private Object value;
private Node next;
int hash;
Node(int hash, Object key, Object value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
Node[] table;
private int size = 8;
public int number = 0;
public MyhashMap() {
table = new Node[size];
}
public int getHash(int v, int length) {
return v & (length - 1);
}
private void resize() {
size *= size;
Node[] newTab = new Node[size];
for(int i=0; i<table.length; i++){
Node cur = table[i];
while(cur != null){
int newhash = getHash(cur.key.hashCode(), size);
Node newnode = newTab[newhash];
Node lastTemp = null;
if (newnode == null) {
newTab[newhash] = cur;
} else {
while (newnode != null) {
newnode = newnode.next;
}
lastTemp.next = cur;
}
cur = cur.next;
}
}
table = newTab;
}
public Object get(Object key) {
int hash = getHash(key.hashCode(), table.length);
Node temp = table[hash];
while (temp != null) {
if (key.equals(temp.key)) {
return temp.value;
} else
temp = temp.next;
}
return null;
}
public void put(Object key, Object value) {
if (number / size > 0.75) {
resize();
}
int hash = getHash(key.hashCode(), table.length);
Node node = new Node(hash, key, value, null);
Node temp = table[node.hash];
Node lastTemp = null;
boolean keyRepeat = false;
if (temp == null) {
table[node.hash] = node;
number++;
} else {
while (temp != null) {
if (temp.key.equals(key)) {
keyRepeat = true;
} else {
lastTemp = temp;
temp = temp.next;
}
}
if (!keyRepeat) {
lastTemp.next = node;
number++;
}
}
}
}
LRU
题目：https://leetcode-cn.com/problems/lru-cache/
class LRUCache {
class LinkedNode {
int key;
int value;
LinkedNode prev;
LinkedNode next;
}
HashMap<Integer, LinkedNode> cache = new HashMap<>();
int size;
int capacity;
LinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new LinkedNode();
tail = new LinkedNode();
head.next = tail;
tail.prev = head;
}
private void addNode(LinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(LinkedNode node) {
LinkedNode prev = node.prev;
LinkedNode next = node.next;
prev.next = next;
next.prev = prev;
}
private void moveToHead(LinkedNode node) {
removeNode(node);
addNode(node);
}
private LinkedNode popTail() {
LinkedNode res = tail.prev;
removeNode(res);
return res;
}
public int get(int key) {
LinkedNode node = cache.get(key);
if (node == null)
return -1;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
LinkedNode node = cache.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
} else {
LinkedNode newNode = new LinkedNode();
newNode.key = key;
newNode.value = value;
cache.put(key, newNode);
addNode(newNode);
size++;
if (size > capacity) {
LinkedNode tail = popTail();
cache.remove(tail.key);
size--;
}
}
}
}
双重锁单例模式
如果不使用volatile关键字，初始化instance时可能会发生重排序。
public class Singleton {
private volatile static Singleton instance;
public static Singleton getInstance(){
if(instance == null){
synchronized (Singleton.class){
if(instance == null){
instance = new Singleton();
}
}
}
return instance;
}
}
两个线程交替运行输出
（三个线程交替输出synchronized两遍）
Object lock = new Object();
Runnable run1 = new Runnable() {
public void run() {
synchronized (lock) {
for (int i = 1; i <= 20; i += 2) {
System.out.println(i);
try {
lock.notify();
lock.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
};
Runnable run2 = new Runnable() {
public void run() {
synchronized (lock) {
for (int i = 2; i <= 20; i += 2) {
System.out.println(i);
try {
lock.notify();
lock.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
};
Thread thread1 = new Thread(run1);
Thread thread2 = new Thread(run2);
thread1.start();
thread2.start();