Do we have capacity method in arrayList() in java?

[srinivas sy]

For vector, by seeing and executing following program we say how vector increases(capacity doubles) its capacity. As i know size is the no of current values stored.

But for ArrayList how to find capacity is increased 50% of its size? Please provide example program to ensure that.




public class A2 {
public static void main(String[] args) {

Vector v=new Vector();

System.out.println(v.capacity());/. default capacity is 10
v.add("abc");
v.add("xyz");
v.add("rqw");
v.add("ip");
v.add("code");
v.add("ranch");
v.add(".com");
v.add("you");
v.add("see");
v.add("for"); //10 elements stored
System.out.println(v);
System.out.println(v.size()); //size is 10
v.add("doubts"); //10+1 (element added newly)...so 11 elements capacity doubled as it was 10 previously now it is 20(doubled)
System.out.println(v.size()); //size11
System.out.println(v.capacity()); //20
}
}


LIKE WISE How can we make sure arraylist increases its size by 50%

[Jude Niroshan]

you can convert that arraylist into a byte stream and get the size of and compare with those values.

[Matthew Brown]

It isn't there because it isn't something you should be worrying about if you're just using the class. The documentation says:

The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

If you want to confirm that it doubles each time, have a look at the source code. But they could change it in a later version if they wanted to. The actual size of the underlying array is an implementation detail.

[Winston Gutkowski]

srinivas sy wrote:LIKE WISE How can we make sure arraylist increases its size by 50%

And just to add to Matthew's point: Why would you want to know this?

The business of Object-Orientation is to hide details that a client doesn't need to know. Do you need to know how the internal combustion engine works in order to drive a car?

Moreover, if the designers of the ArrayList class had specified how the internal capacity is re-sized, they would NEVER be able to change it again - even if it makes sense - because there might be people out there that rely on it.

It should maybe be added that Vector is a legacy class - and capacity() is just one of the possible reasons why.

Winston

[Tim Holloway]

The repeated doubling algorithm is used not only on lists, but also on things like the StringBuilder. Presumably there are some scholarly papers that detail why it's a good approach for most cases.

Don't, however, overlook the fact that there's also an "ensureCapacity" method that can be used to set the capacity more precisely if you need to. The doubling is simply what you get if you let expansion be handled automatically.

I regularly fine-tune my collections (and string building buffers) by taking advantage of the fact that most such objects have constructors that reserve either the precise number of elements that will be held, or in cases where this isn't exact, a "close enough with room to spare" reservation value. Except for hashtables, where a prime number is always a preferable choice.

Note that the code:

// Ensure capacity or grow incrementally (not doubled)
int xfudge = ((x.size() + FUDGE) % FUDGE) * FUDGE;
x.ensureCapacity( xfudge );

This code should re-allocate the underlying collection only every "FUDGE" units, if I have my integer math correct. In other words, "ensureCapacity" doesn't re-allocate unless there isn't already capacity for "xfudge" elements, and "xfudge" only changes value in discrete steps.

[Matthew Brown]

Tim Holloway wrote:The repeated doubling algorithm is used not only on lists, but also on things like the StringBuilder. Presumably there are some scholarly papers that detail why it's a good approach for most cases.

Doubling (or using other multipliers) gives you the "amortized constant time" guarantee that the ArrayList docs mention. That is, on average actions such as addition have constant-time performance, even though the worst case is O(N). Increasing by a fixed amount doesn't give you that guarantee.

[Paul Clapham]

Tim Holloway wrote:Except for hashtables, where a prime number is always a preferable choice.

I've seen this statement before and I don't understand why it's true. My feeling is that it's a myth but I'm open to explanations.

[Campbell Ritchie]

Hadn't noticed that. Are you sure that thing about prime numbers is right?

[Dave Tolls]

Campbell Ritchie wrote:Hadn't noticed that. Are you sure that thing about prime numbers is right?

It's apparently in the maths.
From what I've read, when associated with hash functions that use a prime number modulus, it gives the least number of clashes.
Or something.
It doesn't appear to be a myth.
Don't ask me to expand on that as, frankly, I'm entirely reliant on the mathematicians for this...

[Winston Gutkowski]

Dave Tolls wrote:From what I've read, when associated with hash functions that use a prime number modulus, it gives the least number of clashes.

I think what you say would be true if Java's "hashed" collections used the modulus operator (%), but I'm pretty sire they don't. As I recall, they allocate buckets in powers of two, based on required capacity divided by the loading factor, so that they can simply mask the hash (after a bit of further "mangling", as I recall) in order to get a bucket index.

Frankly, I'm surprised that the designers went to such lengths to avoid using '%' (apparently); but I'm quite sure they've forgotten more about efficiency than I'll ever know, so I don't question it.

Winston

[Campbell Ritchie]

Winston Gutkowski wrote: . . . would be true if Java's "hashed" collections used the modulus operator (%), but I'm pretty sure they don't. . . .

They definitely don't.

They use h & c − 1
…where h is hash code and c is array's capacity (values.length).
That has two advantages when you are using arrays where length == 2ⁿ

1: & runs in two clock cycles whereas the % operator may take 32 clock cycles.

2: & only returns a negative result when both its operands are negative.

If you use % the sign of the result is the same as that of the left operand; since approx 50% of hash codes are negative, you need to use an abs function too, otherwise you suffer an out of bounds Exception.

[Campbell Ritchie]

Actually, & takes 1 clock cycle and − takes 1: that makes my 2 cycles.