Win a copy of TDD for a Shopping Website LiveProject this week in the Testing forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Jeanne Boyarsky
  • Tim Cooke
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
  • Frits Walraven
Bartenders:
  • Piet Souris
  • Himai Minh

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

 
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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%



 
Ranch Hand
Posts: 135
5
Eclipse IDE Postgres Database Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
you can convert that arraylist into a byte stream and get the size of and compare with those values.
 
Bartender
Posts: 4568
9
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Saloon Keeper
Posts: 25455
178
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:



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
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Marshal
Posts: 27211
87
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Marshal
Posts: 75631
354
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hadn't noticed that. Are you sure that thing about prime numbers is right?
 
Rancher
Posts: 4801
50
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Marshal
Posts: 75631
354
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
    Marshal
    Posts: 75631
    354
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Actually, & takes 1 clock cycle and − takes 1: that makes my 2 cycles.
     
    You showed up just in time for the waffles! And this tiny ad:
    Free, earth friendly heat - from the CodeRanch trailboss
    https://www.kickstarter.com/projects/paulwheaton/free-heat
    reply
      Bookmark Topic Watch Topic
    • New Topic