网易 java两道笔试编程题
1、创建一个同步机制。如实现4个线程，其中两个线程加1，两个线程对变量减1.
2、写一个与实现hashMap相似的类。
（1）类长度是定值，超出长度，抛出异常或等待删除一个后再插入。
（2）写一个具有延迟添加的方法put(Key k,Value v,long time)，超过时间后失效。
（3）如果一个类近期被get()过，那么延长失效时间。
[解决办法]
1.
public class MyThread extends Thread{ public static int num = 0; public void run(){ add(); //根据题目意思不同线程 调用 add 或 del } public synchronized void math(int type){ switch(type){ case 1: ++num; break; case 2: --num; break; } } public void add(){ math(1); } public void del(){ math(2); }}
[解决办法]
public class Test {
static int j = 0;
public static void main(String[] args){
MyThread1 mt1 = new MyThread1();
mt1.start();
MyThread1 mt2 = new MyThread1();
mt2.start();
MyThread2 mt3 = new MyThread2();
mt3.start();
MyThread2 mt4 = new MyThread2();
mt4.start();
}
static class MyThread1 extends Thread{
public void run(){
while(true){
try{
j = ++j;
this.sleep(1000);
System.out.println("此时j的值是"+j);
}catch(InterruptedException e){
e.printStackTrace();
}
}
}
}
static class MyThread2 extends Thread{
public void run(){
while(true){
try{
j = --j;
this.sleep(1000);
System.out.println("此时j的值是"+j);
}catch(InterruptedException e){
e.printStackTrace();
}
}
}
}
[解决办法]
第二题 第三问不明白...
import java.util.HashMap;public class H extends HashMap { private final int size = 2; public Object put(Object key, Object value, long nas) { if (this.size() > size) {//设置最大长度 throw new IllegalStateException(); } synchronized (this) { try { this.wait(nas);//设置延迟插入 } catch (Exception e) { e.printStackTrace(); } return super.put(key, value); } }}class Test { public static void main(String[] args) { H m = new H(); m.put("s", "ss", 1000L); m.put("d", "ss", 1000L); m.put("F", "ss", 1000L); m.put("f", "ss", 1000L); System.out.println(m.get("s")); }}
[解决办法]
public class TestThread { private int j; public TestThread(int j) {this.j = j;} private synchronized void inc(){ j++; System.out.println(j + "--Inc--" + Thread.currentThread().getName()); } private synchronized void dec(){ j--; System.out.println(j + "--Dec--" + Thread.currentThread().getName()); } public void run() { (new Dec()).start(); new Thread(new Inc()).start(); (new Dec()).start(); new Thread(new Inc()).start(); } class Dec extends Thread { public void run() { for(int i=0; i<100; i++){ dec(); } } } class Inc implements Runnable { public void run() { for(int i=0; i<100; i++){ inc(); } } } public static void main(String[] args) { (new TestThread(5)).run(); }}
[解决办法]
package util;import java.util.Iterator;import java.util.LinkedList;public class MapTester { public static void main(String[] args) throws InterruptedException { final MyMap<Integer, String> map = new MyMap<Integer, String>(); new Thread() { @Override public void run() { try { Thread.sleep(1000 * 4); map.remove(0); } catch (Exception e) {} } }.start(); for (int i = 0; i < 30; i++) { map.put(i, Integer.toBinaryString(i)); map.get(i % 2); } }}@SuppressWarnings("unchecked")class MyMap<K, V> { public static int DEFAULT_CAPACITY = 20; public static long DEFAULT_EXPIRATION = 1000 * 10; private int capacity; private int size; private LinkedList[] entries; private LinkedList<RegisterObject> queue; private long expiration; public MyMap() { this(DEFAULT_CAPACITY); } public MyMap(int capacity) { this(capacity, DEFAULT_EXPIRATION); } public MyMap(int capacity, long expiration) { this.capacity = capacity - capacity / 3; this.entries = new LinkedList[capacity]; this.queue = new LinkedList<RegisterObject>(); this.expiration = expiration; this.size = 0; } public synchronized void put(K key, V value) { if (isFull()) { RegisterObject registerObject = null; while (registerObject == null) { registerObject = queue.removeFirst(); if (!registerObject.isValid()) { registerObject = null; } } long timeLeft = registerObject.getTimeLeft(); if (timeLeft > 0) { try { System.err.println("已经的到达最大容量 等待清理过期元素"); wait(timeLeft); } catch (InterruptedException e) { e.printStackTrace(); } } clear(); } int index = getIndex(key); if (entries[index] == null) { entries[index] = new LinkedList(); } LinkedList list = entries[index]; for (Iterator it = list.iterator(); it.hasNext();) { if (((ElementObject) it.next()).getKey().hashCode() == key.hashCode()) { it.remove(); break; } } size++; list.addLast(new ElementObject(key, value, queue)); } public synchronized V get(K key) { ElementObject result = search(key); if (result != null) { long timeout = result.getRegisterObject().getTimeLeft(); if (timeout > 0) { clearCreateTime(result); return (V) result.getValue(); } else { remove(key); } } return null; } public synchronized V remove(K key) { int index = getIndex(key); LinkedList list = entries[index]; ElementObject elementObject = null; if (list != null) { for (Iterator it = list.iterator(); it.hasNext();) { elementObject = (ElementObject) it.next(); if (elementObject.getKey().hashCode() == key.hashCode()) { it.remove(); elementObject.getRegisterObject().setValid(false); System.err.println("删除元素 key:" + elementObject.getKey() + ";value:" + elementObject.getValue()); notifyAll(); size--; return (V) elementObject.getValue(); } } } return null; } private synchronized ElementObject search(K key) { int index = getIndex(key); LinkedList list = entries[index]; ElementObject result = null; if (list != null) { for (Object obj : list) { if (((ElementObject) obj).getKey().hashCode() == key.hashCode()) { result = (ElementObject) obj; } } } return result; } private int getIndex(K key) { return Math.abs(key.hashCode() % capacity); } private synchronized boolean isFull() { clear(); return size == DEFAULT_CAPACITY; } private synchronized void clear() { for (Iterator<RegisterObject> it = queue.iterator(); it.hasNext();) { RegisterObject registerObject = it.next(); if (!registerObject.isValid()) { it.remove(); } else if (registerObject.getTimeLeft() <= 0) { it.remove(); remove((K) registerObject.getKey()); } else { return; } } } private void clearCreateTime(ElementObject elementObject) { RegisterObject oldRegisterObject = elementObject.getRegisterObject(); RegisterObject newRegisterObject = new RegisterObject(elementObject.getKey()); elementObject.setRegisterObject(newRegisterObject); queue.add(newRegisterObject); oldRegisterObject.setValid(false); } class RegisterObject { private long createTime; private boolean isValid; private Object key; public RegisterObject(Object key) { this(System.currentTimeMillis(), key); } public RegisterObject(long createTime, Object key) { this(createTime, true, key); } public RegisterObject(long createTime, boolean isValid, Object key) { this.createTime = createTime; this.isValid = isValid; this.key = key; } public long getTimeLeft() { return this.createTime + expiration - System.currentTimeMillis(); } public long getCreateTime() { return createTime; } public void setCreateTime(long createTime) { this.createTime = createTime; } public boolean isValid() { return isValid; } public void setValid(boolean isValid) { this.isValid = isValid; } public Object getKey() { return key; } public void setKey(Object key) { this.key = key; } } class ElementObject { private Object key; private Object value; private RegisterObject registerObject; public ElementObject() { } public ElementObject(Object key, Object value, LinkedList<RegisterObject> queue) { this.key = key; this.value = value; this.registerObject = new RegisterObject(key); queue.addLast(registerObject); } public Object getKey() { return key; } public void setKey(Object key) { this.key = key; } public Object getValue() { return value; } public void setValue(Object value) { this.value = value; } public RegisterObject getRegisterObject() { return registerObject; } public void setRegisterObject(RegisterObject registerObject) { this.registerObject = registerObject; } }}
[解决办法]
没那么复杂吧。以下是我的实现：
public class HashMapTest extends HashMap {
private static int size = 2;
private static int time = 1000*10;
private static long begintime= System.currentTimeMillis();
@Override
public Object get(Object key) {
this.begintime = System.currentTimeMillis();
return super.get(key);
}
/**
* 如果Key中不包含即将要增加的key，且长度大于等size
*/
@Override
public Object put(Object key, Object value) {
Object o=super.get(key);
if(super.size() >=this.size && !super.containsKey(key))
{
System.out.println("数量达到上限，不能增加！");
return o;
}
if(System.currentTimeMillis() - this.begintime > time){
System.out.println("操作超时，不能再放值！");
return o;
}else{
return super.put(key, value);
}
}
}
//测试类：
package test;
import java.util.Iterator;
import java.util.Set;
public class HashMapTestCeshi {
/**
* @param args
* @throws InterruptedException
*/
public static void main(String[] args) throws InterruptedException {
// TODO Auto-generated method stub
HashMapTest hmt=new HashMapTest();
hmt.put("1", 1);
hmt.put("3", 3);
try{
Set set=hmt.keySet();
Iterator iter=set.iterator();
while(iter.hasNext()){
System.out.println(hmt.get(iter.next()));
}
hmt.put("1","adfafaf");
}catch(Exception e){
e.printStackTrace();
}
System.out.println("------------------");
try{
Set set=hmt.keySet();
Iterator iter=set.iterator();
while(iter.hasNext()){
System.out.println(hmt.get(iter.next()));
}
}catch(Exception e){
e.printStackTrace();
}
}
}
[解决办法]
第2个,我是这么想的，不过就是超时清理掉过期条目不知道怎么弄，如果每个 map 都弄个线程去清理太影响性能了：
1.继承自 HashMap 改写其中的 put 和 get 就可以了。
2.在 put/putAll/get 这几个方法中，去 它的 value 进行一个 wrap，比如原来 put("Key","Value") 我们把这个 "Key" 加壳成 new TimestampedKey("Key", new Date())，然后在 get 时再去壳，这个 TimestampedKey 改写 compareTo, hashCode, equals 之类的方法，让它支持排序，
3.以后在 put 时当发现已经满了的话，先查找这个 key 对应的“壳”，拿出来看它是否已经过期了。如果过期了就替换掉。否则进行超时等待在新增加的长度锁上阻塞指定的时间，当时间到了或被唤醒的话，再检查一次长度，这次如果依然没有空间就抛出超时异常。
4.每次 get 命中了一个条目时，更新这个条目的到期时间，比如，原来刚 put 进来时是 5 秒超时，我们在 get 一次时让它变成 5 + 5/2，下一次再 get 时更新成 (5+5/2) + (5+5/2)/2，依次类推。