高速缓存来实现使用数组 - ArrayIndexOutOfBoundsException异常（JAVA） [英] Cache Implemented Using an Array - ArrayIndexOutOfBoundsException (Java)
问题描述
我模拟Web缓存替换算法。我有可用于对那些以串行方式到达缓存对象缓存和L的请求类型请求的N个对象。
请求的目的是通过其的int字段REQID区分（从0数字ID多达N-1）。我不得不重写等于能够比较请求对象。
我使用数组实现一个高速缓存 - 一种简单，朴素，静态数组
缓存充满类型请求的对象，而具有最大尺寸M：
/ **最大缓存大小* /
私人诠释米;/ ** *高速缓存/
私人请求[] =缓存新的Request [M]。
我有插入，驱逐和缓存中的对象的替代品。
我有也作为ArrayDeque实现的最后K个请求的滑动窗口：
/ **最大窗口大小* /
私人诠释k;/ **窗口* /
私人deque的＆lt;请求＆GT;窗口=新ArrayDeque＆lt;请求＆GT;（K）;
数值M和K在构造函数初始化，并在主要设置（）。
我把对象的得分（在最后K个请求的滑动窗口请求数）在HashMap：
/ **地图REQID（K）的 - 得分（V）* /
地图＆LT;整数，整数GT;得分了;
我保持在高速缓存项的得分方面下令缓存，具有最高得分为在左端和得分最低的是在合适的端
由于这样的事实，当我有一个缓存命中一个项目的分值增加1，而当我有一个项目的请求，从窗口项的分数减1下降，在这种情况下我可能有高速缓存相关项目在缓存中的下一个项目在其左侧或分别交换位置正确，重新排序。所以，我应该能够知道cache中的每个（随机）项的索引在任何给定的时间。为此，我使用所谓的反整型字段和一个HashMap叫的位置：
/ **计数器=高速缓存中的位置* /
私人诠释柜台;/ **地图请求ID（K）的 - 计数器（V）* /
私人地图＆LT;整数，整数GT;职位;
最后，我用一个inCache地图，以避免循环，在查找操作：
/ **地图与布尔标志检查项目（请求ID）是否在高速缓存或不* /
私人地图＆LT;整数，布尔＆GT; inCache;
和一个isMoreThanOne标志，以避免调用当前缓存大小吸气时，这个尺寸大的：
/ **标志在高速缓存*超过1项/
私人布尔isMoreThanOne;
的原因是，由于我的高速缓存是香草阵列而不是一个ArrayList，它不具有一个大小（）方法，以及长度字段是给定，而不是当前缓存大小的固定容量。因此，为了得到当前高速缓存大小，我应该做到以下几点（因为我不是100％，请大家看看，如果它是正确的）：
/ **
*返回一个适合当前高速缓存大小
* @返回当前高速缓存大小
* /
公众诠释getCacheSize（）{ //临时柜台
诠释计数= 0;//扫描缓存
的for（int i = 0; I＆LT; this.cache.length;我++）{ //只要项目不空
如果（this.cache [I]！= NULL）{ //增加1计数器
数+ = 1; } //当第一个空项发现
其他{ //跳出循环
打破; }}//返回当前高速缓存大小（计数器）
返回计数;
}
这是长，但neccessary介绍后，这里是缓存插入的code，其中我得到一个ArrayIndexOutOfBoundsException：
/ **
*高速缓存插入操作
* @参数请求被插入到高速缓存请求的项
* /
公共无效doCacheInsert（请求请求）{ //如果这是第一项插入到高速缓存
如果（getCacheSize（）== 0）{ //设置计数器
计数器= M-1; //索引柜台插入项目
this.cache [计数器] =请求; //这里我有消息 //把位置索引位置列表
this.positions.put（request.reqID，计数器）;}//如果这不是插入到高速缓冲存储器的第一项
其他{ //如果缓存尚未达到其最大尺寸
如果（getCacheSize（）！= this.cacheWindowLFU.length）{ //减少1计数器
计数器 - = 1; //索引柜台插入项目
this.cache [计数器] =请求; //把位置索引位置列表
this.positions.put（request.reqID，计数器）; //设置isMoreThanOne标志
isMoreThanOne = TRUE; } //如果缓存达到其最大尺寸
其他{ //重新设置计数器M-1
计数器= M-1; //索引柜台插入项目
this.cache [计数器] =请求; }}//激活标志在inCache地图项目
this.inCache.put（request.reqID，真）;}
我得到的消息几乎就在该方法的开始，在第1，如果在该行块：
//插入索引项柜台
this.cache [计数器] =请求;
...我真的不知道为什么！
编辑：这是我的构造函数：
/ **
*构造
* @参数m最大缓存大小
* @参数最多为K，窗口大小
项目* @参数N多
* /
公共算法（INT男，INT K，INT N）{ //初始化最大缓存大小和最大窗口大小
this.M = M;
this.K = K;//初始化计数器
计数器= 0;//初始化isMoreThanOne标志
isMoreThanOne = FALSE;//分配inCache，winFreqs和地图定位
inCache =新的HashMap＆LT;整数，布尔＆GT;（N）;
分数=新的HashMap＆LT;整数，整数GT;（N）;
位置=新的HashMap＆LT;整数，整数GT;（N）;}
这是主要的相关部分（），这是主类中：
//东西.....（例如SIM奔跑等＃）//项目数
numItems的INT = 20;//请求数
INT numR = 40;//最大缓存大小
INT M = 5;//最大窗口尺寸
INT K = 3;//东西......（例如新一代的请求，统计等的开始）算法类型// instantianate对象
算法ALG =新算法（M，K，项目数）;//东西.....（例如查找，插入，更换，命中＃，命中率等）
以下变量为0，由于初始化的实例变量的初始化的阶段。
/ **最大缓存大小* /
私人诠释米; //默认被设置为0/ ** *高速缓存/
私人请求[] =缓存新的Request [M]。 //默认设置为[]（空数组）
移动缓存初始化的构造，所以在创建算法实例缓存被初始化：
/ ** *高速缓存/
私人请求[]缓存;公共算法（INT M）{
this.M = M;
this.cache =新要求[M]。 //设置的请求[M]
}
这是结果的块初始化命令的在Java中是如下：
- 静态实例变量（只运行一次，而第一类负载）
- 的静态初始化块（只运行一次，而第一类负载）
- 超构造函数（如果有的话）
- 实例变量（运行每创建一个新实例时）
- ＆GT; M和高速缓存设置为0 - 非静态初始化块（运行每创建一个新实例时）
- 构造
- ＆GT;根据参数M更新
根据上述规则，你可以看到 M 最初默认为0值的 M 当时传递给缓存这与0大小（空数组），从而导致ArrayIndexOutOfBoundsException异常（不管什么价值被分配到 M 构造函数中，已初始化缓存为0的大小）。
I simulate a web cache replacement algorithm. I have N objects of type Request available for caching and L requests for those objects that arrive to the cache in a serial fashion.
Request objects are distinguished by their int field reqID (a numeric ID from 0 up to N-1). I have override equals to be able to compare Request objects.
I implement a cache using an array - a simple, plain, static array.
The cache is filled with objects of type Request and has a max size M:
/** Max cache size */
private int M;
/** Cache */
private Request[] cache = new Request[M];
I have insertions, evictions and replacements of objects in the cache.
I have also a sliding window of the last K requests implemented as an ArrayDeque:
/** Max window size */
private int K;
/** Window */
private Deque<Request> window = new ArrayDeque<Request>(K);
Values M and K are initialized at the constructor and set at main().
I keep the score (request count in a sliding window of last K requests) of the objects in a HashMap:
/** Map of reqID (K) - Score (V) */
Map<Integer, Integer> score;
I keep the cache ordered in terms of the score of the cached items, with the highest score being at the left end and the lowest score being at the right end.
Due to the fact that when I have a cache hit for an item its score is increased by 1 while when I have a request for an item dropped from the window the score of that item is decreased by 1, in those cases I might have cache reordering with the relevant item exchanging position in the cache with the next item at its left or right, respectively. Therefore, I should be able to know the index of each (random) item in the cache at any given time. For that purpose, I use an integer field called counter and a HashMap called positions:
/** Counter = position in the cache */
private int counter;
/** Map of ReqID (K) - Counter (V) */
private Map<Integer, Integer> positions;
Finally, I use an inCache map in order to avoid the "for loop" in lookup operation:
/** Map with boolean flags to check whether an item (ReqID) is in cache or not */
private Map<Integer, Boolean> inCache;
and an isMoreThanOne flag to avoid calling the getter for the current cache size when this size is large:
/** Flag for more than 1 items in cache */
private boolean isMoreThanOne;
The reason is that, since my cache is a vanilla array and not an ArrayList, it does not have a size() method, and length field is the fixed capacity given, not the current cache size. Therefore, in order to get the current cache size, I should do the following (please take a look since I am not 100% if it is correct):
/**
* Getter for current cache size
* @return Current cache size
*/
public int getCacheSize() {
// temp counter
int count = 0;
// scan the cache
for(int i = 0; i < this.cache.length; i++) {
// as long as the items are not null
if(this.cache[i] != null) {
// increase the counter by 1
count += 1;
}
// when the first null item found
else {
// jump out of the loop
break;
}
}
// return the current cache size (counter)
return count;
}
After that long but neccessary introduction, here is the code of cache insertion where I get an ArrayIndexOutOfBoundsException:
/**
* Cache insertion operation
* @param request The requested item that is inserted into the cache
*/
public void doCacheInsert(Request request) {
// if this is the first item inserted into the cache
if(getCacheSize() == 0) {
// set counter
counter = M-1;
// insert item at index counter
this.cache[counter] = request; // HERE I HAVE THE MESSAGE
// put position index into positions list
this.positions.put(request.reqID, counter);
}
// if this is not the first item inserted into the cache
else {
//if the cache has not reached its max size
if(getCacheSize() != this.cacheWindowLFU.length) {
// decrease counter by 1
counter -= 1;
// insert item at index counter
this.cache[counter] = request;
// put position index into positions list
this.positions.put(request.reqID, counter);
// set isMoreThanOne flag
isMoreThanOne = true;
}
// if the cache has reached its max size
else {
// reset counter to M-1
counter = M-1;
// insert item at index counter
this.cache[counter] = request;
}
}
// activate flag for item in inCache map
this.inCache.put(request.reqID, true);
}
I get the message almost right at the beginning of this method, at the 1st if block at the line:
// insert item at index counter
this.cache[counter] = request;
... and I really don't know why!
EDIT: Here is my constructor:
/**
* Constructor
* @param M Max cache size
* @param K Max window size
* @param N Number of items
*/
public Algorithm(int M, int K, int N) {
// initialize max cache size and max window size
this.M = M;
this.K = K;
// initialize counter
counter = 0;
// initialize isMoreThanOne flag
isMoreThanOne = false;
// allocate inCache, winFreqs, and positions maps
inCache = new HashMap<Integer, Boolean>(N);
scores = new HashMap<Integer, Integer>(N);
positions = new HashMap<Integer, Integer>(N);
}
And here is the relevant part of main() which is inside Main class:
// stuff..... (e.g. # of sim runs etc.)
// number of items
int numItems = 20;
// number of requests
int numR = 40;
// maximum cache size
int M = 5;
// maximum window size
int K = 3;
// stuff...... (e.g. generation of requests, start of statistics etc.)
// instantianate object of type Algorithm
Algorithm alg = new Algorithm(M, K, numItems);
// stuff..... (e.g. lookup, insertion, replacement, # of hits, hit rate etc.)
The following variables are initialized with 0 due to instance variables initialization phase.
/** Max cache size */
private int M; //set to 0 by default
/** Cache */
private Request[] cache = new Request[M]; //set to [] by default (an empty array)
Move cache initialization to the constructor, so that cache is initialized while creating Algorithm instance:
/** Cache */
private Request[] cache;
public Algorithm(int M) {
this.M = M;
this.cache = new Request[M]; // set to Request[M]
}
This is the result of initialization blocks order in Java which is as follows:
- static instance variables (runs only ONCE while first class load)
- static init block (runs only ONCE while first class load)
- super-constructors (if any)
- instance variables (runs every time a new instance is created)
--> M and cache set to 0 - non-static init block (runs every time a new instance is created)
- constructor
--> M updated according to the parameter
Based on the above rule you can see that M was originally defaulted to 0. Value of M was then passed to cache which was allocated with 0 size (an empty array) thus leading to ArrayIndexOutOfBoundsException (no matter what value was assigned to M within constructor, already initialized cache was of 0 size).
这篇关于高速缓存来实现使用数组 - ArrayIndexOutOfBoundsException异常（JAVA）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
